dc.contributor.author | Gairing, M. | en |
dc.contributor.author | Lücking, T. | en |
dc.contributor.author | Mavronicolas, Marios | en |
dc.contributor.author | Monien, Burkhard | en |
dc.creator | Gairing, M. | en |
dc.creator | Lücking, T. | en |
dc.creator | Mavronicolas, Marios | en |
dc.creator | Monien, Burkhard | en |
dc.date.accessioned | 2019-11-13T10:40:06Z | |
dc.date.available | 2019-11-13T10:40:06Z | |
dc.date.issued | 2004 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53958 | |
dc.description.abstract | We consider the problem of routing n users on m parallel links, under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. Thus, the problem is equivalent to the correspondingly restricted problem of assigning n jobs to m parallel machines. In a pure Nash equilibrium, no user may improve its own individual cost (delay) by unilaterally switching to another link from its set of allowed links. As our main result, we introduce a polynomial time algorithm to compute from any given assignment a pure Nash equilibrium with non-increased makospan. The algorithm gradually changes a given assignment by pushing unsplittable user traffics through a network that is defined by the users and the links. Here, we use ideas from blocking flows. Furthermore, we use similar techniques as in the generic PREFLOW-PUSH algorithm to approximate a schedule with minimum makespan, gaining an improved approximation factor of 2 - 1/w1 for identical links, where w1 is the largest user traffic. We extend this result to related links, gaining an approximation factor of 2. Our approximation algorithms run in polynomial time. We close with tight upper bounds on the coordination ratio for pure Nash equilibria. | en |
dc.source | Conference Proceedings of the Annual ACM Symposium on Theory of Computing | en |
dc.source | Proceedings of the 36th Annual ACM Symposium on Theory of Computing | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-4544276263&partnerID=40&md5=f5936bd436b17fc4c5891706c9ca3758 | |
dc.subject | Problem solving | en |
dc.subject | Algorithms | en |
dc.subject | Approximation theory | en |
dc.subject | Computational complexity | en |
dc.subject | Scheduling | en |
dc.subject | Polynomials | en |
dc.subject | Parallel processing systems | en |
dc.subject | Approximation algorithms | en |
dc.subject | Routers | en |
dc.subject | Nash equilibria | en |
dc.subject | Selfish routing | en |
dc.subject | Unsplittable flow | en |
dc.subject | Machine scheduling | en |
dc.title | Computing Nash equilibria for scheduling on restricted parallel links | en |
dc.type | info:eu-repo/semantics/conferenceObject | |
dc.description.startingpage | 613 | |
dc.description.endingpage | 622 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Conference Object | en |
dc.description.notes | <p>Sponsors: Association for Computing Machinery, SIGACT | en |
dc.description.notes | Conference code: 63566 | en |
dc.description.notes | Cited By :65</p> | en |