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 on-line 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(rootn)-competitive algorithms.

Crescenzi, P., Gambosi, G., Nicosia, G., Penna, P., Unger, W. (2003). Online load balancing made simple: Greedy strikes back. In AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS.

Online load balancing made simple: Greedy strikes back

GAMBOSI, GIORGIO;
2003-01-01

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 on-line 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(rootn)-competitive algorithms.
30th International Colloquium on Automata, Languages and Programming (ICALP 2003)
EINDHOVEN, NETHERLANDS
JUN 30-JUL 04, 2003
Municipal Eindhoven, Sodexho, Oce, Res Sch IPA, European Educ Forum, Springer Verlag, Elsevier, Philips Res, Atos Origin, Pallas Athena, Pearson Educ Benelux, ABE Fdn
Rilevanza internazionale
2003
Settore INF/01 - INFORMATICA
English
FLOW
Intervento a convegno
Crescenzi, P., Gambosi, G., Nicosia, G., Penna, P., Unger, W. (2003). Online load balancing made simple: Greedy strikes back. In AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS.
Crescenzi, P; Gambosi, G; Nicosia, G; Penna, P; Unger, W
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/43447
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact