Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 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 Khanna dblp 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
 URL of the conference: http://www.siam.org/meetings/da13/ URL for downloading the paper: 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

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: January Pages: 1243-1252 Year*: 2013 VG Wort Pages: 10 ISBN/ISSN: Sequence Number: DOI:

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