ECCC-Report TR00-001https://eccc.weizmann.ac.il/report/2000/001Comments and Revisions published for TR00-001en-usFri, 14 Jan 2000 15:36:51 +0200
Paper TR00-001
| On-Line Load Balancing for Related Machines |
Piotr Berman,
Moses Charikar,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2000/001
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+\sqrt{8}\approx 5.828$ for the deterministic
version, and $3.31/\ln 2.155 \approx 4.311$ for 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.
Fri, 14 Jan 2000 15:36:51 +0200https://eccc.weizmann.ac.il/report/2000/001