Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2022) | last year (2021) | two years ago (2020) | Notes URL

Action:

login to update
Options:




Library Locked Library locked




Author, Editor(s)
Author(s):
Christodoulou, George
Kovacs, Annamaria
van Stee, Rob		dblp
dblp
dblp
Not MPG Author(s):
Christodoulou, George
Kovacs, Annamaria

BibTeX cite key*:

ChKoSt2013

Title

Title*:

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

Journal

Journal Title*:

Theoretical Computer Science
Journal's URL:

http://www.journals.elsevier.com/theoretical-computer-science

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier
Publisher's URL:


Publisher's
Address:


ISSN:

0304-3975

Vol, No, pp, Date

Volume*:

489-490
Number:


Publishing Date:

June 2013

Pages*:

88-98
Number of
VG Pages:

12

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(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 approximation guarantee of $2+\eps$,
significantly improving on the previous upper bound of $\min(m,(2+\eps)s_m/s_1)$.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

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


BibTeX Entry:

@ARTICLE{ChKoSt2013,
AUTHOR = {Christodoulou, George and Kovacs, Annamaria and van Stee, Rob},
 TITLE = {A truthful constant approximation for maximizing the minimum load on related machines},
 JOURNAL = {Theoretical Computer Science},
 PUBLISHER = {Elsevier},
 YEAR = {2013},
 VOLUME = {489-490},
 PAGES = {88--98},
 MONTH = {June},
 ISBN = {0304-3975},
}

Entry last modified by Rob van Stee, 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
01/14/2014 03:51:10 PM
Revision
0.



Editor
Rob van Stee



Edit Date
14/01/2014 15:51:10