We study the load balancing problem in the context of a set of clients eachwishing to run a job on a server selected among a subset of permissible servers forthe particular client. We consider two different scenarios. In selfish load balancing,each client is selfish in the sense that it chooses, among its permissible servers, torun its job on the server having the smallest latency given the assignments of thejobs 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 toone of its permissible servers. Here, we assume that the clients aim to optimize someglobal criterion but in an online fashion. A natural local optimization criterion thatcan be used by each client when making its decision is to assign its job to that serverthat gives the minimum increase of the global objective. This gives rise to greedyonline solutions. The aim of this paper is to determine how much the quality of loadbalancing is affected by selfishness and greediness.We characterize almost completely the impact of selfishness and greediness inload balancing by presenting new and improved, tight or almost tight bounds on theprice of anarchy of selfish load balancing as well as on the competitiveness of thegreedy algorithm for online load balancing when the objective is to minimize thetotal latency of all clients on servers with linear latency functions. In addition, weprove a tight upper bound on the price of stability of linear congestion games.

Tight Bounds for Selfish and Greedy Load Balancing

Flammini M;
2011

Abstract

We study the load balancing problem in the context of a set of clients eachwishing to run a job on a server selected among a subset of permissible servers forthe particular client. We consider two different scenarios. In selfish load balancing,each client is selfish in the sense that it chooses, among its permissible servers, torun its job on the server having the smallest latency given the assignments of thejobs 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 toone of its permissible servers. Here, we assume that the clients aim to optimize someglobal criterion but in an online fashion. A natural local optimization criterion thatcan be used by each client when making its decision is to assign its job to that serverthat gives the minimum increase of the global objective. This gives rise to greedyonline solutions. The aim of this paper is to determine how much the quality of loadbalancing is affected by selfishness and greediness.We characterize almost completely the impact of selfishness and greediness inload balancing by presenting new and improved, tight or almost tight bounds on theprice of anarchy of selfish load balancing as well as on the competitiveness of thegreedy algorithm for online load balancing when the objective is to minimize thetotal latency of all clients on servers with linear latency functions. In addition, weprove a tight upper bound on the price of stability of linear congestion games.
Load balancing; Price of anarchy and stability; Congestion games; Online algorithms
File in questo prodotto:
File Dimensione Formato  
2011_Algorithmica_61_Caragiannis.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 1.02 MB
Formato Adobe PDF
1.02 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/20.500.12571/2382
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 65
  • ???jsp.display-item.citation.isi??? 43
social impact