Journal Article
@Article
Artikel in Fachzeitschrift


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(s)

Author(s):

Epstein, Leah
Levin, Asaf
van Stee, Rob

dblp
dblp
dblp

Not MPG Author(s):

Epstein, Leah
Levin, Asaf

BibTeX cite key*:

EpLeSt11a

Title

Title*:

Max-min online allocations with a reordering buffer


bcover_jour2.dvi (115.57 KB); bcover_jour5_rev_sec.pdf (168.2 KB)

Journal

Journal Title*:

SIAM Journal on Discrete Mathematics

Journal's URL:

http://www.siam.org/journals/sidma.php

Download URL
for the article:

http://dx.doi.org/10.1137/100794006

Language:

English

Publisher

Publisher's
Name:

SIAM

Publisher's URL:

http://www.siam.org/

Publisher's
Address:

Philadelphia, PA

ISSN:

0895-4801

Vol, No, pp, Date

Volume*:

25

Number:

3

Publishing Date:

2011

Pages*:

1230-1250

Number of
VG Pages:

21

Page Start:

1230

Page End:

1250

Sequence Number:


DOI:

10.1137/100794006

Note, Abstract, ©

Note:


(LaTeX) Abstract:

We consider online scheduling so as to maximize the minimum load,
using a reordering buffer which can store some of the jobs before
they are assigned irrevocably to machines.
For $m$ identical machines, we show an upper bound of $H_{m-1}+1$ for a buffer of size $m-1$. A competitive ratio below $H_m$ is not possible with any fixed buffer size, and it requires a buffer of size $\Omega(m/\log m)$ to get a ratio of $O(\log m)$. For uniformly related machines, we show that a buffer of size $m+1$ is sufficient to get a competitive ratio of $m$, which is best possible for any fixed sized buffer.
We show similar results (but with different constructions) for
the restricted assignment model. We give tight bounds for two machines in all the three models.

These results sharply contrast to the (previously known) results
which can be achieved without the usage of a reordering buffer,
where it is not possible to get a ratio below a competitive
ratio of $m$ already for identical machines, and it is impossible
to obtain an algorithm of finite competitive ratio in the other
two models, even for $m=2$. Our results strengthen the previous
conclusion that a reordering buffer is a powerful tool and it
allows a significant decrease in the competitive ratio of online
algorithms for scheduling problems. Another interesting aspect of
our results is that our algorithm for identical machines imitates
the behavior of a greedy algorithm on (a specific set of)
related machines, whereas our algorithm for related machines
completely ignores the speeds until all jobs have arrived, and then only uses the relative order of the speeds.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

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:

@ARTICLE{EpLeSt11a,
AUTHOR = {Epstein, Leah and Levin, Asaf and van Stee, Rob},
TITLE = {Max-min online allocations with a reordering buffer},
JOURNAL = {SIAM Journal on Discrete Mathematics},
PUBLISHER = {SIAM},
YEAR = {2011},
NUMBER = {3},
VOLUME = {25},
PAGES = {1230--1250},
ADDRESS = {Philadelphia, PA},
ISBN = {0895-4801},
DOI = {10.1137/100794006},
}


Entry last modified by Anja Becker, 02/09/2012
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:26:04 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Anja Becker
Rob van Stee
Thomas Sauerwald
Rob van Stee
Rob van Stee
Edit Dates
09.02.2012 10:43:55
12/12/2011 04:02:36 PM
03/03/2011 05:58:17 PM
01-25-2011 15:08:38
12-09-2010 15:26:04
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
bcover_jour2.dvi
File Attachment Icon
bcover_jour5_rev_sec.pdf