TY - JOUR
T1 - On-Line Load Balancing for Related Machines
AU - Berman, Piotr
AU - Charikar, Moses
AU - Karpinski, Marek
N1 - Funding Information:
2Supported by Stanford School of Engineering Groswith Fellowship, an ARO MURI Grant DAAH04-96-1-0007 and NSF Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. E-mail: moses@ cs.stanford.edu.
Funding Information:
3Partially supported by the DFG Grant KA 673 4-1, by the ESPRIT BR Grants 7097, 21726, EC-US 030, and by the Max-Planck Research Prize. E-mail: [email protected].
PY - 2000/4
Y1 - 2000/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0009004515&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0009004515&partnerID=8YFLogxK
U2 - 10.1006/jagm.1999.1070
DO - 10.1006/jagm.1999.1070
M3 - Article
AN - SCOPUS:0009004515
SN - 0196-6774
VL - 35
SP - 108
EP - 121
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -