MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Epstein, Leah
Levin, Asaf
van Stee, Rob		dblp
dblp
dblp
Not MPG Author(s):
Epstein, Leah
Levin, Asaf
Editor(s):
Sanjeev Khannadblp
Not MPII Editor(s):
Sanjeev Khanna
BibTeX cite key*:
EpLeSt13
Title, Booktitle
Title*:
A unified approach to truthful scheduling on related machines
monotone_PTAS_SODA_proceedings.pdf (154.45 KB)
Booktitle*:
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Event, URLs
Conference URL::
http://www.siam.org/meetings/da13/
Downloading URL:
Event Address*:
New Orleans, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
6 January 2013
Event End Date:
8 January 2013
Publisher
Name*:
SIAM
URL:
Address*:
Philadelphia, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
January
Pages:
1243-1252
Year*:
2013
VG Wort Pages:
10
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTAS's) for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the $\ell_p$ norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone algorithms have the property that an increase in the speed of a machine cannot decrease the amount of work assigned to it.

The key idea of our novel method is to show that for goal functions that are sufficiently well-behaved functions of the machine loads, it is possible to compute in polynomial time a highly
structured nearly optimal schedule.
An interesting aspect of our approach is that, in contrast to all known approximation schemes, we avoid rounding any job sizes or speeds throughout. We can therefore find the \emph{exact} best structured schedule using dynamic programming. The state space encodes a sufficient amount of information such that no postprocessing is needed, allowing an elegant and relatively simple analysis without any special cases. The monotonicity is a consequence of the fact that we find the {\it best} schedule in a specific collection of schedules.

Monotone approximation schemes have an important role in the emerging area of algorithmic mechanism design.
In the game-theoretical setting of these scheduling problems there is a social goal, which is one of the objective functions that we study. Each machine is controlled by a selfish single-parameter agent, where its private information is its cost of processing a unit sized job, which is also the inverse of
the speed of its machine. Each agent wishes to maximize its own profit, defined as the payment it receives from the mechanism minus its cost for processing all jobs assigned to it, and places a bid which corresponds to its private information.
For each one of the problems, we show that we can calculate payments that guarantee truthfulness in an efficient manner. Thus, there exists a dominant strategy where agents report their true speeds, and we show the existence of a truthful mechanism which can be implemented in polynomial time, where the social goal is approximated within a factor of $1+\eps$ for every $\eps>0$.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{EpLeSt13,
AUTHOR = {Epstein, Leah and Levin, Asaf and van Stee, Rob},
 EDITOR = {Sanjeev Khanna},
 TITLE = {A unified approach to truthful scheduling on related machines},
 BOOKTITLE = {Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013},
 PUBLISHER = {SIAM},
 YEAR = {2013},
 PAGES = {1243--1252},
 ADDRESS = {New Orleans, USA},
 MONTH = {January},
 ISBN = {2160-1455},
}

Entry last modified by Stephanie Müller, 02/17/2014
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
11/14/2012 02:06:03 PM
Revisions
2.
1.
0.

Editor(s)
Stephanie Müller
Rob van Stee
Rob van Stee

Edit Dates
04.02.2013 15:00:21
01/16/2013 04:14:37 PM
11/14/2012 02:06:03 PM

File Attachment Icon
monotone_PTAS_SODA_proceedings.pdf