Computing Nash equilibria for scheduling on restricted parallel links
Ημερομηνία
2010Συγγραφέας
Gairing, M.Lücking, T.
Mavronicolas, Marios
Monien, Burkhard
ISSN
1432-4350Source
Theory of Computing SystemsVolume
47Issue
2Pages
405-432Google Scholar check
Keyword(s):
Metadata
Εμφάνιση πλήρους εγγραφήςΕπιτομή
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.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Article
PADS: An approach to modeling resource demand and supply for the formal analysis of hierarchical scheduling
Philippou, Anna; Lee, I.; Sokolsky, O. (2012)As real-time embedded systems become more complex, resource partitioning is increasingly used to guarantee real-time performance. Recently, several compositional frameworks of resource partitioning have been proposed using ...
-
Conference Object
Scheduling workflows with budget constraints
Sakellariou, R.; Zhao, H.; Tsiakkouri, E.; Dikaiakos, Marios D. (Springer Science and Business Media, LLC, 2007)Grids are emerging as a promising solution for resource and computation demanding applications. However, the heterogeneity of resources in Grid computing, complicates resource management and scheduling of applications. In ...
-
Conference Object
Dynamic transmission scheduling for packet radio networks
Panayiotou, Christos G.; Cassandras, C. G. (1998)