Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784
Greece

phone: +30 210 7275122
fax: +30 210 7275114

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

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, 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

@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},
}