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):

Christodoulou, George
Kovacs, Annamaria
van Stee, Rob

dblp
dblp
dblp

Not MPG Author(s):

Christodoulou, George
Kovacs, Annamaria

Editor(s):

Saberi, Amin

dblp

Not MPII Editor(s):

Saberi, Amin

BibTeX cite key*:

ChKoSt10

Title, Booktitle

Title*:

A truthful constant approximation for maximizing the minimum load on related machines

Booktitle*:

Internet and Network Economics : 6th International Workshop, WINE 2010

Event, URLs

URL of the conference:

http://www.stanford.edu/group/wine/

URL for downloading the paper:


Event Address*:

Stanford, USA

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

13 December 2010

Event End Date:

17 December 2010

Publisher

Name*:

Springer

URL:

http://www.springer-ny.com/

Address*:

Berlin

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

6484

Number:


Month:


Pages:

182-193

Year*:

2010

VG Wort Pages:


ISBN/ISSN:

978-3-642-17571-8

Sequence Number:


DOI:

10.1007/978-3-642-17572-5_15



Note, Abstract, ©


(LaTeX) 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)$.



Download
Access Level:

Priviledged Users

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{ChKoSt10,
AUTHOR = {Christodoulou, George and Kovacs, Annamaria and van Stee, Rob},
EDITOR = {Saberi, Amin},
TITLE = {A truthful constant approximation for maximizing the minimum load on related machines},
BOOKTITLE = {Internet and Network Economics : 6th International Workshop, WINE 2010},
PUBLISHER = {Springer},
YEAR = {2010},
VOLUME = {6484},
PAGES = {182--193},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Stanford, USA},
ISBN = {978-3-642-17571-8},
DOI = {10.1007/978-3-642-17572-5_15},
}


Entry last modified by Anja Becker, 12/17/2010
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
12/09/2010 03:55:47 PM
Revision
1.
0.


Editor
Anja Becker
Rob van Stee


Edit Date
17.12.2010 13:54:35
12-09-2010 15:55:47