research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleBetter bounds for online load balancing on unrelated machines
Bibtex cite IDRACTI-RU1-2008-2
Booktitle 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008)
Year published 2008
Pages 972-981
Publisher Society for Industrial and Applied Mathematics
Location San Francisco, California
Address Philadelphia, PA, USA
We study the problem of scheduling permanent jobs on un- related machines when the objective is to minimize the Lp norm of the machine loads. The problem is known as load balancing under the Lp norm. We present an improved up- per bound for the greedy algorithm through simple analy- sis; this bound is also shown to be best possible within the class of deterministic online algorithms for the problem. We also address the question whether randomization helps on- line load balancing under Lp norms on unrelated machines; this is a challenging question which is open for more than a decade even for the L2 norm. We provide a positive answer to this question by presenting the »rst randomized online algorithms which outperform deterministic ones under any (integral) Lp norm for p = 2; :::; 137. Our algorithms es- sentially compute in an online manner a fractional solution to the problem and use the fractional values to make ran- dom choices. The local optimization criterion used at each step is novel and rather counterintuitive: the values of the fractional variables for each job correspond to ░ows at an ap- proximate Wardrop equilibrium for an appropriately de»ned non-atomic congestion game. As corollaries of our analysis and by exploiting the relation between the Lp norm and the makespan of machine loads, we obtain new competitive algo- rithms for online makespan minimization, making progress in another longstanding open problem.
Caragiannis, Ioannis
soda08.pdf (main file)
Publication ID102