A lower bound for randomized on-line scheduling algorithms

B. Chen; A. Vliet, van; G.J. Woeginger

doi:10.1016/0020-0190(94)00110-3

A lower bound for randomized on-line scheduling algorithms

B. Chen, A. Vliet, van, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

54 Citaten (Scopus)

1 Downloads (Pure)

Samenvatting

We prove that any randomized algorithm for on-line scheduling jobs on m identical parallel machines must have a worst case ratio at least mm/(mm-(m-1)m) for every m, which tends to e/(e-1) ˜ 1.58 as m¿8. This answers a question posed in a recent paper by Bartal, Fiat, Karloff and Vohra.

Originele taal-2	Engels
Pagina's (van-tot)	219-222
Tijdschrift	Information Processing Letters
Volume	51
Nummer van het tijdschrift	5
DOI's	https://doi.org/10.1016/0020-0190(94)00110-3
Status	Gepubliceerd - 1994

Toegang tot document

10.1016/0020-0190(94)00110-3

Vingerafdruk Duik in de onderzoeksthema's van 'A lower bound for randomized on-line scheduling algorithms'. Samen vormen ze een unieke vingerafdruk.

Citeer dit

@article{410f550825f948898fd0d4a7f722760f,

title = "A lower bound for randomized on-line scheduling algorithms",

abstract = "We prove that any randomized algorithm for on-line scheduling jobs on m identical parallel machines must have a worst case ratio at least mm/(mm-(m-1)m) for every m, which tends to e/(e-1) ˜ 1.58 as m¿8. This answers a question posed in a recent paper by Bartal, Fiat, Karloff and Vohra.",

author = "B. Chen and {Vliet, van}, A. and G.J. Woeginger",

year = "1994",

doi = "10.1016/0020-0190(94)00110-3",

language = "English",

volume = "51",

pages = "219--222",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - A lower bound for randomized on-line scheduling algorithms

AU - Chen, B.

AU - Vliet, van, A.

AU - Woeginger, G.J.

PY - 1994

Y1 - 1994

N2 - We prove that any randomized algorithm for on-line scheduling jobs on m identical parallel machines must have a worst case ratio at least mm/(mm-(m-1)m) for every m, which tends to e/(e-1) ˜ 1.58 as m¿8. This answers a question posed in a recent paper by Bartal, Fiat, Karloff and Vohra.

AB - We prove that any randomized algorithm for on-line scheduling jobs on m identical parallel machines must have a worst case ratio at least mm/(mm-(m-1)m) for every m, which tends to e/(e-1) ˜ 1.58 as m¿8. This answers a question posed in a recent paper by Bartal, Fiat, Karloff and Vohra.

U2 - 10.1016/0020-0190(94)00110-3

DO - 10.1016/0020-0190(94)00110-3

M3 - Article

VL - 51

SP - 219

EP - 222

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 5

ER -