MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Epstein, Leah
van Stee, Rob		dblp
dblp
Not MPG Author(s):
Epstein, Leah
Editor(s):
Laber, Eduardo Sany
Bornstein, Claudson
Noguiera, Loana Tito
Faria, Luerbio		dblp
dblp
dblp
dblp
Not MPII Editor(s):
Laber, Eduardo Sany
Bornstein, Claudson
Noguiera, Loana Tito
Faria, Luerbio
BibTeX cite key*:
vanStee2008a
Title, Booktitle
Title*:
Maximizing the minimum load for selfish agents
cover16.dvi (108.21 KB)
Booktitle*:
LATIN 2008: Theoretical Informatics, 8th Latin American Symposium
Event, URLs
Conference URL::
http://www.latin08.org/
Downloading URL:
http://www.springerlink.com/content/m4041512q2616208/fulltext.pdf
Event Address*:
Búzios, Brazil
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
7 April 2008
Event End Date:
11 April 2008
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4957
Number:
Month:
April
Pages:
264-275
Year*:
2008
VG Wort Pages:
12
ISBN/ISSN:
0302-9743
Sequence Number:
DOI:
10.1007/978-3-540-78773-0_23
Note, Abstract, ©
(LaTeX) Abstract:
We consider the problem of maximizing the minimum load for
machines that are controlled by selfish agents, who are only
interested in maximizing their own profit. Unlike the classical
load balancing problem, this problem
has not been considered for selfish agents until now.

For a constant number of machines, $m$, we show a
monotone polynomial time approximation scheme (PTAS) with running
time that is linear in the number of jobs. It uses a new
technique for reducing the number of jobs while remaining close
to the optimal solution. We also present an FPTAS for the classical
machine covering problem, i.e., where no selfish agents are involved
(the previous best result for this case was a PTAS)
and use this to give a monotone FPTAS.

Additionally, we give a monotone approximation algorithm with
approximation ratio $\min(m,(2+\varepsilon)s_1/s_m)$ where $\varepsilon>0$ can
be chosen arbitrarily small and $s_i$ is the (real) speed of
machine $i$. Finally we give improved results for two machines.
Keywords:
algorithmic game theory, scheduling, max-min fairness
Download
Access Level:
Public

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:

@INPROCEEDINGS{vanStee2008a,
AUTHOR = {Epstein, Leah and van Stee, Rob},
 EDITOR = {Laber, Eduardo Sany and Bornstein, Claudson and Noguiera, Loana Tito and Faria, Luerbio},
 TITLE = {Maximizing the minimum load for selfish agents},
 BOOKTITLE = {LATIN 2008: Theoretical Informatics, 8th Latin American Symposium},
 PUBLISHER = {Springer},
 YEAR = {2008},
 VOLUME = {4957},
 PAGES = {264--275},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {B{\'u}zios, Brazil},
 MONTH = {April},
 ISBN = {0302-9743},
 DOI = {10.1007/978-3-540-78773-0_23},
}

Entry last modified by Rob van Stee, 12/10/2010
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)
Rob van Stee		Created
01/12/2009 12:48:03
Revisions
4.
3.
2.
1.
0.		Editor(s)
Rob van Stee
Uwe Brahm
Rob van Stee
Rob van Stee
Rob van Stee		Edit Dates
12-10-2010 15:35:08
03/20/2009 02:55:47 PM
03/20/2009 09:57:51 AM
01/12/2009 01:45:42 PM
01/12/2009 12:48:03 PM

File Attachment Icon
cover16.dvi