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
TitleTight bounds for selfish and greedy load balancing
Bibtex cite IDRACTI-RU1-2006-38
Booktitle 33rd International Colloquium on Automata, Languages, and Programming (ICALP 2006)
Year published 2006
Volume 4051/2006
Pages 311-322
Publisher Springer Berlin / Heidelberg
Note LNCS 4051, Part I
DOI 10.1007/11786986
We study the load balancing problem in the context of a set of clients each wishing to run a job on a server selected among a subset of permissible servers for the particular client. We consider two different scenarios. In selfish load balancing, each client is selfish in the sense that it selects to run its job to the server among its permissible servers having the smallest latency given the assignments of the jobs of other clients to servers. In online load balancing, clients appear online and, when a client appears, it has to make an irrevocable decision and assign its job to one of its permissible servers. Here, we assume that the clients aim to optimize some global criterion but in an online fashion. A natural local optimization criterion that can be used by each client when making its decision is to assign its job to that server that gives the minimum increase of the global objective. This gives rise to greedy online solutions. The aim of this paper is to determine how much the quality of load balancing is affected by selfishness and greediness. We characterize almost completely the impact of selfishness and greediness in load balancing by presenting new and improved, tight or almost tight bounds on the price of anarchy and price of stability of selfish load balancing as well as on the competitiveness of the greedy algorithm for online load balancing when the objective is to minimize the total latency of all clients on servers with linear latency functions.
Caragiannis, Ioannis
Flamini, M
Kaklamanis, Christos
Kanellopoulos, Panagiotis
Moscardelli, L
3.pdf (main file)
Publication ID96