A lower bound for randomized on-line scheduling algorithms

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

    Research output: Contribution to journalArticleAcademicpeer-review

    40 Citations (Scopus)
    1 Downloads (Pure)


    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 languageEnglish
    Pages (from-to)219-222
    JournalInformation Processing Letters
    Issue number5
    Publication statusPublished - 1994


    Dive into the research topics of 'A lower bound for randomized on-line scheduling algorithms'. Together they form a unique fingerprint.

    Cite this