Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2023) | last year (2022) | two years ago (2021) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Seiden, Steve S. dblp
 BibTeX cite key*: Seiden2000

 Title
 Title*: Online randomized multiprocessor scheduling

 Journal

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