research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleEfficient coordination mechanisms for unrelated machine scheduling
Bibtex cite IDRACTI-RU1-2009-2
Booktitle 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)
Year published 2009
Pages 815-824
Location New York
Note to appear
We present three new coordination mechanisms for schedul- ing n sel¯sh jobs on m unrelated machines. A coordination mechanism aims to mitigate the impact of sel¯shness of jobs on the e±ciency of schedules by de¯ning a local schedul- ing policy on each machine. The scheduling policies induce a game among the jobs and each job prefers to be sched- uled on a machine so that its completion time is minimum given the assignments of the other jobs. We consider the maximum completion time among all jobs as the measure of the e±ciency of schedules. The approximation ratio of a coordination mechanism quanti¯es the e±ciency of pure Nash equilibria (price of anarchy) of the induced game. Our mechanisms are deterministic, local, and preemptive in the sense that the scheduling policy does not necessarily process the jobs in an uninterrupted way and may introduce some idle time. Our ¯rst coordination mechanism has approxima- tion ratio O(logm) and always guarantees that the induced game has pure Nash equilibria to which the system con- verges in at most n rounds. This result improves a recent bound of O(log2 m) due to Azar, Jain, and Mirrokni and, similarly to their mechanism, our mechanism uses a global ordering of the jobs according to their distinct IDs. Next we study the intriguing scenario where jobs are anonymous, i.e., they have no IDs. In this case, coordination mechanisms can only distinguish between jobs that have diffeerent load characteristics. Our second mechanism handles anonymous jobs and has approximation ratio O ¡ logm log logm ¢ although the game induced is not a potential game and, hence, the exis- tence of pure Nash equilibria is not guaranteed by potential function arguments. However, it provides evidence that the known lower bounds for non-preemptive coordination mech- anisms could be beaten using preemptive scheduling poli- cies. Our third coordination mechanism also handles anony- mous jobs and has a nice \cost-revealing" potential func- tion. Besides in proving the existence of equilibria, we use this potential function in order to upper-bound the price of stability of the induced game by O(logm), the price of an- archy by O(log2 m), and the convergence time to O(log2 m)- approximate assignments by a polynomial number of best- response moves. Our third coordination mechanism is the ¯rst that handles anonymous jobs and simultaneously guar- antees that the induced game is a potential game and has bounded price of anarchy.
Caragiannis, Ioannis
soda09b.pdf (main file)
Publication ID518