Elias Koutsoupias / Publications

George Christodoulou, Elias Koutsoupias, Angelina Vidali: A Lower Bound for Scheduling Mechanisms. Algorithmica 55(4): 729-740 (2009).

G. Christodoulou, E. Koutsoupias, and A. Vidali. A lower bound for scheduling mechanisms. SODA 2007: 1163-1170.

Download: pdf ps

Abstract

We study the mechanism design problem of scheduling tasks on $n$ unrelated machines in which the machines are the players of the mechanism. The problem was proposed and studied in the seminal paper of Nisan and Ronen on algorithmic mechanism design, where it was shown that the approximation ratio of mechanisms is between 2 and $n$. We improve the lower bound to $1+\sqrt{2}$ for 3 or more machines.

Bib

@article{CKV09,
  author    = {George Christodoulou and
               Elias Koutsoupias and
               Angelina Vidali},
  title     = {A Lower Bound for Scheduling Mechanisms},
  journal   = {Algorithmica},
  volume    = {55},
  number    = {4},
  year      = {2009},
  pages     = {729-740},
  ee        = {http://dx.doi.org/10.1007/s00453-008-9165-3},
  notes	    = {An earlier version appeared in SODA 2007}
}

@string{SODA07 = {Proceedings of the Eighteenth Annual ACM-SIAM Symposium
               on Discrete Algorithms (SODA)}}

@inproceedings{CKV07,
  author =       {G. Christodoulou and E. Koutsoupias and A. Vidali},
  title =        {A lower bound for scheduling mechanisms.},
  booktitle = {SODA},
  month     = {7--9 } #jan,
  year      = {2007},
  pages     = {1163-1170},
  address   = {New Orleans, Louisiana, USA},
  ee        = {http://doi.acm.org/10.1145/1283383.1283508},
}