de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

A Truthful Constant Approximation for Maximizing the Minimum Load on Related Machines

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44250

Christodoulou,  George
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44834

Kovacs,  Annamaria
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45543

van Stee,  Rob
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Christodoulou, G., Kovacs, A., & van Stee, R. (2010). A Truthful Constant Approximation for Maximizing the Minimum Load on Related Machines. In A. Saberi (Ed.), Internet and Network Economics (pp. 182-193). Berlin: Springer. doi:10.1007/978-3-642-17572-5_15.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1613-F
Abstract
Designing truthful mechanisms for scheduling on related machines is a very important problem in single-parameter mechanism design. We consider the covering objective, that is we are interested in maximizing the minimum completion time of a machine. This problem falls into the class of problems where the optimal allocation can be truthfully implemented. A major open issue for this class is whether truthfulness affects the polynomial-time implementation. We provide the first constant factor approxi\-mation for deterministic truthful mechanisms. In particular we come up with a $2+\eps$ approximation guarantee, significantly improving on the previous upper bound of $\min(m,(2+\eps)s_m/s_1)$.