MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Epstein, Leah
Levin, Asaf
van Stee, Rob		dblp
dblp
dblp
Not MPG Author(s):
Epstein, Leah
Levin, Asaf
Editor(s):
Abramsky, Samson
Gavoille, Cyril
Kirchner, Claude
Meyer auf der Heide, Friedhelm
Spirakis, Paul G.		dblp
dblp
dblp
dblp
dblp
Not MPII Editor(s):
Abramsky, Samson
Gavoille, Cyril
Kirchner, Claude
Meyer auf der Heide, Friedhelm
Spirakis, Paul G.
BibTeX cite key*:
EpLeSt10
Title, Booktitle
Title*:
Max-min online allocations with a reordering buffer
Booktitle*:
Automata, Languages and Programming : 37th International Colloquium, ICALP 2010
Event, URLs
Conference URL::
http://icalp10.inria.fr/
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-14165-2_29
Event Address*:
Bordeaux, France
Language:
English
Event Date*
(no longer used):
Organization:
European Association for Theoretical Computer Science (EATCS)
Event Start Date:
6 July 2010
Event End Date:
10 July 2010
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
6198
Number:
Month:
July
Pages:
336-347
Year*:
2010
VG Wort Pages:
12
ISBN/ISSN:
9-783642-14164-5
Sequence Number:
DOI:
10.1007/978-3-642-14165-2_29
Note, Abstract, ©
(LaTeX) Abstract:
We consider a scheduling problem where each job is controlled by a
selfish agent, who is only interested in minimizing its own cost,
which is defined as the total load on the machine that its job is
assigned to. We consider the objective of maximizing the minimum load
(cover) over the machines.
Unlike the regular makespan minimization problem, which was extensively
studied in a game theoretic context, this problem has not been
considered in this setting before.

We study the price of anarchy (\poa) and the price of stability (\pos).
Since these measures are unbounded already for two uniformly
related machines, we focus on identical machines. We show that
the $\pos$ is 1, and we derive tight bounds on the $\poa$ for
$m\leq6$ and nearly tight bounds for general $m$. In particular,
we show that the $\poa$ is at least 1.691 for larger $m$ and at
most 1.7. Hence, surprisingly, the $\poa$ is less than the $\poa$
for the makespan problem, which is 2. To achieve the upper bound
of 1.7, we make an unusual use of weighting functions. Finally,
in contrast we show that the mixed $\poa$ grows exponentially with
$m$ for this problem, although it is only $\Theta(\log m/\log
\log m)$ for the makespan.

In addition we consider a similar setting with a different
objective which is minimizing the maximum ratio between the loads
of any pair of machines in the schedule. We show that under this
objective for general $m$ the $\pos$ is 1, and the $\poa$ is 2.
Download
Access Level:
Internal

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{EpLeSt10,
AUTHOR = {Epstein, Leah and Levin, Asaf and van Stee, Rob},
 EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
 TITLE = {Max-min online allocations with a reordering buffer},
 BOOKTITLE = {Automata, Languages and Programming : 37th International Colloquium, ICALP 2010},
 PUBLISHER = {Springer},
 YEAR = {2010},
 ORGANIZATION = {European Association for Theoretical Computer Science (EATCS)},
 VOLUME = {6198},
 PAGES = {336--347},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Bordeaux, France},
 MONTH = {July},
 ISBN = {9-783642-14164-5},
 DOI = {10.1007/978-3-642-14165-2_29},
}

Entry last modified by Manuel Lamotte-Schubert, 03/21/2011
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 15:48:54
Revisions
2.
1.
0.

Editor(s)
Manuel Lamotte-Schubert
Anja Becker
Rob van Stee

Edit Dates
21.03.2011 08:41:33
04.01.2011 13:46:31
12-09-2010 15:48:54