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 Library locked




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

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
monotone_PTAS_SODA_proceedings.pdf