Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-Reports 1999 Copyright 1999 Universität Bonn, Institut für Informatik, Abt. V 85210 On-line Load Balancing for Related Machines Piotr Berman, Moses Charikar, Marek Karpinski [Download PostScript] [Download PDF] 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. Last Change: 11/05/14 at 10:14:36  English Universität Bonn -> Institut für Informatik -> Abteilung V