Randomized on-line scheduling on two uniform machines

L. Epstein, J. Noga, S.S. Seiden, J. Sgall, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    69 Citations (Scopus)

    Abstract

    We study the problem of on-line scheduling on two uniform machines with speeds 1 and s*1.A /+1.61803 competitive deterministic algorithm was already known. We present the "rst randomized results for this problem: We show that randomization does not help for speeds s*2, but does help for all s(2. We present a simple memoryless randomized algorithm with competitive ratio (4!s) (1#s)/4)1.56250. We analyse other randomized algorithms that demonstrate that the randomized competitive ratio is at most 1.52778 for any s. These algorithms are barely random, i.e. they use only a constant number of random bits. Finally, we present a 1#s/(s2#s#1) competitive deterministic algorithm for the preemptive version of this problem. For any s, it is best possible even among randomized preemptive algorithms.
    Original languageEnglish
    Pages (from-to)71-92
    JournalJournal of Scheduling
    Volume4
    Issue number2
    DOIs
    Publication statusPublished - 2001

    Fingerprint

    Dive into the research topics of 'Randomized on-line scheduling on two uniform machines'. Together they form a unique fingerprint.

    Cite this