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 | 2010 | |
dc.identifier.issn | 1432-4350 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53954 | |
dc.description.abstract | We consider the problem of routing nusers 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. So, this problem is equivalent to the correspondingly restricted scheduling problem of assigning njobs to m parallel machines. In a Nash equilibrium, no user may improve its own Individual Cost (latency) by unilaterally switching to another link from its set of allowed links. For identical links, we present, as our main result, a polynomial time algorithm to compute from any given assignment a Nash equilibrium with non-increased makespan. The algorithm gradually transforms the assignment by pushing the unsplittable user traffics through a flow network, which is constructed from the users and the links. The algorithm uses ideas from blocking flows. Furthermore, we use techniques simular to those in the generic PreflowPush algorithm to approximate in polynomial time a schedule with optimum makespan. This results to an improved approximation factor of 2-1/w1 for identical links, where w1 is the largest user traffic, and to an approximation factor of 2 for related links. © 2009 Springer Science+Business Media, LLC. | en |
dc.source | Theory of Computing Systems | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-77952957764&doi=10.1007%2fs00224-009-9191-9&partnerID=40&md5=0f284511dc6df9d33d738513f8ddf522 | |
dc.subject | Game theory | en |
dc.subject | Telecommunication networks | en |
dc.subject | Scheduling | en |
dc.subject | Polynomial approximation | en |
dc.subject | Nash equilibria | en |
dc.subject | Parallel machine | en |
dc.subject | Scheduling algorithms | en |
dc.subject | Algorithmic game theory | en |
dc.subject | Approximation factor | en |
dc.subject | Computation of Nash equilibria | en |
dc.subject | Polynomial-time algorithms | en |
dc.subject | Preflow-push algorithms | en |
dc.subject | Scheduling problem | en |
dc.subject | Scheduling restricted machines | en |
dc.subject | Unsplittable flow | en |
dc.title | Computing Nash equilibria for scheduling on restricted parallel links | en |
dc.type | info:eu-repo/semantics/article | |
dc.identifier.doi | 10.1007/s00224-009-9191-9 | |
dc.description.volume | 47 | |
dc.description.issue | 2 | |
dc.description.startingpage | 405 | |
dc.description.endingpage | 432 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.description.notes | <p>Cited By :7</p> | en |
dc.source.abbreviation | Theory Comput.Syst. | en |