On-Line Load Balancing for Related Machines

TitleOn-Line Load Balancing for Related Machines
Publication TypeTechnical Report
Year of Publication1997
AuthorsBerman, P., Charikar M., & Karpinski M.
Other Numbers1074

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 approx 5.828 for the deterministic version, and 3.31/ln 2.155 approx 4.311for its randomized variant, improving the previous competitive ratios of 8 and 2e approx 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.

Bibliographic Notes

ICSI Technical Report TR-97-007

Abbreviated Authors

P. Berman, M. Charikar, and M. Karpinski

ICSI Publication Type

Technical Report