Computing Nash equilibria for scheduling on restricted parallel links
SourceTheory of Computing Systems
Google Scholar check
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
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 ...
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 ...
Dynamic transmission scheduling for packet radio networks Panayiotou, Christos G.; Cassandras, C. G. (1998)