A lower bound for randomized on-line scheduling algorithms

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer 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-2Engels
    Pagina's (van-tot)219-222
    TijdschriftInformation Processing Letters
    Volume51
    Nummer van het tijdschrift5
    DOI's
    StatusGepubliceerd - 1994

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

    Citeer dit