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:








Author, Editor(s)

Author(s):

Seiden, Steve S.

dblp



BibTeX cite key*:

Seiden2000

Title

Title*:

Online randomized multiprocessor scheduling

Journal

Journal Title*:

Algorithmica

Journal's URL:

http://link.springer-ny.com/link/service/journals/00453/

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer-ny.com/

Publisher's
Address:

New York, USA

ISSN:

0178-4617

Vol, No, pp, Date

Volume*:

28

Number:

2

Publishing Date:

2000

Pages*:

173-216

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

The use of randomization in online multiprocessor scheduling is studied. The problem of scheduling independent jobs on m machines online originates with Graham [16]. While the deterministic case of this problem has been studied extensively, little work has been done on the randomized case. For m= 2 a randomized 4/3-competitive algorithm was found by Bartal et al. A randomized algorithm for m 3 is presented. It achieves competitive ratios of 1.55665, 1.65888, 1.73376, 1.78295, and 1.81681, for m = 3, 4, 5, 6,7 , respectively. These competitive
ratios are less than the best deterministic lower bound for m=3,4,5 and less than the best known deterministic competitive ratio for m = 3,4,5,6,7 . Two models of multiprocessor scheduling with rejection are studied. The first is the model of Bartal et al. Two randomized algorithms for this model are presented. The first algorithm performs well for small m , achieving competitive ratios of 3/2 , $(7 + \sqrt{129})/10 < 1.83579$ , $(5 + 2 \sqrt{22})/7 < 2.05441$ for m=2,3,4 , respectively. The second algorithm outperforms the first for m 5 . It beats the deterministic algorithm of Bartal et al. for all m = 5 ,. . ., 1000 . It is conjectured that this is true for all m . The second model differs in that preemption is allowed. For this model, randomized algorithms
are presented which outperform the best deterministic algorithm for small m .

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:


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:

@ARTICLE{Seiden2000,
AUTHOR = {Seiden, Steve S.},
TITLE = {Online randomized multiprocessor scheduling},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2000},
NUMBER = {2},
VOLUME = {28},
PAGES = {173--216},
ADDRESS = {New York, USA},
ISBN = {0178-4617},
}


Entry last modified by Uwe Brahm, 03/02/2010
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)
Anja Becker
Created
03/14/2001 03:25:49 PM
Revisions
2.
1.
0.

Editor(s)
Uwe Brahm
Anja Becker
Anja Becker

Edit Dates
05/02/2001 11:28:27 AM
14.03.2001 15:28:41
14.03.2001 15:28:17