Title: A note on On-line Load Balancing for related Machines
Abstract:We describe an on-line algorithm for scheduling permanent jobs on related machines. It achieves the competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic version, and $3.31/\ln 2.155 \a...We describe an on-line algorithm for scheduling permanent jobs on related machines. It 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$.Read More
Publication Year: 1996
Publication Date: 1996-09-01
Language: en
Type: article
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot