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

Research output: Contribution to journal › Article › Academic › peer-review

40 Citations (Scopus)

1 Downloads (Pure)

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.

Original language	English
Pages (from-to)	219-222
Journal	Information Processing Letters
Volume	51
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(94)00110-3
Publication status	Published - 1994

Access to Document

10.1016/0020-0190(94)00110-3

Cite this

@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

SN - 0020-0190

VL - 51

SP - 219

EP - 222

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

A lower bound for randomized on-line scheduling algorithms

Abstract

Access to Document

Fingerprint

Cite this