On-Line Load Balancing for Related Machines
Title | On-Line Load Balancing for Related Machines |
Publication Type | Technical Report |
Year of Publication | 1997 |
Authors | Berman, P., Charikar M., & Karpinski M. |
Other Numbers | 1074 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1997/tr-97-007.pdf |
Bibliographic Notes | ICSI Technical Report TR-97-007 |
Abbreviated Authors | P. Berman, M. Charikar, and M. Karpinski |
ICSI Publication Type | Technical Report |