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 Goto entry point

 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

 (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},