English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Online randomized multiprocessor scheduling

Seiden, S. S. (2000). Online randomized multiprocessor scheduling. Algorithmica, 28(2), 173-216.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Seiden, Steve S.1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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 .

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-022000
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 518153
Other: Local-ID: C1256428004B93B8-DF47934D72B62779C1256A0F004F44D1-Seiden2000
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithmica
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 28 (2) Sequence Number: - Start / End Page: 173 - 216 Identifier: ISSN: 0178-4617