Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Online Load Balancing Made Simple: Greedy Strikes Back
| |
|
Online Load Balancing Made Simple: Greedy Strikes Back
Pilu Crescenzi5  , Giorgio Gambosi6 , Gaia Nicosia7 , Paolo Penna8 and Walter Unger9
| (5) |
Dipartimento di Sistemi ed Informatica, Università di Firenze, via C. Lombroso 6/17, I-50134 Firenze, Italy |
| (6) |
Dipartimento di Matematica, Università di Roma “Tor Vergata”, via della Ricerca Scientifica, I-00133 Roma, Italy |
| (7) |
Dipartimento di Informatica e Automazione, Università degli studi “Roma Tre”, via della Vasca Navale 79, I-00146 Roma, Italy |
| (8) |
Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, via S. Allende 2, I-84081 Baronissi (SA), Italy |
| (9) |
RWTH Aachen, Ahornstrasse 55, 52056 Aachen, Germany |
Abstract
We provide a new simpler approach to the on-line load balancing problem in the case of restricted assignment of temporary
weighted tasks. The approach is very general and allows to derive online distributed algorithms whose competitive ratio is
characterized by some combinatorial properties of the underlying graph representing the problem.
The effectiveness of our approach is shown by the hierarchical server model introduced by Bar-Noy et al ’99. In this case, our method yields simpler and distributed algorithms whose competitive ratio is at least as good as the
existing ones. Moreover, the resulting algorithms and their analysis turn out to be simpler. Finally, in all cases the algorithms
are optimal up to a constant factor.
Some of our results are obtained via a combinatorial characterization of those graphs for which our technique yields O(
)-competitive algorithms.
A similar title is used in [13] for a facility location problem.
supported by the European Project IST-2001-33135, Critical Resource Sharing for Cooperation in Complex Systems (CRESCCO).
Work partially done while at the Dipartimento di Matematica, Università di Roma “Tor Vergata” and while at the Institut für
Theoretische Informatik, ETH Zentrum.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|