Bio and Coordinates

Publications

Talks

Courses

For Students

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

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

E. Koutsoupias and A. Vidali. A Lower Bound of 1+phi for Truthful Scheduling Mechanisms. MFCS, 2007: 454-464.
Download: pdf ps

Abstract

We give an improved lower bound for the approximation ratio of truthful mechanisms for the unrelated machines scheduling problem. The mechanism design version of the problem which was proposed and studied in the seminal paper of Nisan and Ronen is at the core of the emerging area of Algorithmic Game Theory. The new lower bound is a step towards the final resolution of this important problem.

Bib 

@string{MFCS07 = {Mathematical Foundations of Computer Science (MFCS)}}

@InProceedings{KV07,
  author =       {E. Koutsoupias and A. Vidali},
  title =        {A Lower Bound of 1+phi for Truthful Scheduling Mechanisms},
  booktitle =    MFCS07,
  pages = 	 {454-464},
  year =         2007,
  month =        {26-31 } #aug,
  address =      {Krumlov, Czech Republic},
}