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

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

URL of the conference:

http://icalp10.inria.fr/

URL for downloading the paper:

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
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:48:54 PM
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