A lower bound for randomized on-line scheduling algorithms

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

    Research output: Contribution to journalArticleAcademicpeer-review

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

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

  • Cite this