On-line load balancing for related machines

Piotr Berman, Moses Charikar, Marek Karpinski

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    16 Scopus citations


    We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + √8 ≈ 5.828 for the deterministic version, and 3.31/ln 2.155 ≈ 4.311 for its randomized variant, improving the previous competitive ratios of 8 and 2e ≈ 5.436. We also prove lower bounds of 2.4380 on the competitive ratio of deterministic algorithms and 1.8372 on the competitive ratio of randomized algorithms for this problem.

    Original languageEnglish (US)
    Title of host publicationAlgorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings
    EditorsFrank Dehne, Jorg-Rudiger Sack, Andrew Rau-Chaplin, Roberto Tamassia
    PublisherSpringer Verlag
    Number of pages10
    ISBN (Print)3540633073, 9783540633075
    StatePublished - 1997
    Event5th International Workshop on Algorithms and Data Structures, WADS 1997 - Halifax, Canada
    Duration: Aug 6 1997Aug 8 1997

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other5th International Workshop on Algorithms and Data Structures, WADS 1997

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'On-line load balancing for related machines'. Together they form a unique fingerprint.

    Cite this