caa a22 4500 445805218 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00453-010-9427-8 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9427-8 Tight Bounds for Selfish and Greedy Load Balancing [Elektronische Daten] [Ioannis Caragiannis, Michele Flammini, Christos Kaklamanis, Panagiotis Kanellopoulos, Luca Moscardelli] 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 chooses, among its permissible servers, to run its job on the server 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 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. In addition, we prove a tight upper bound on the price of stability of linear congestion games. Springer Science+Business Media, LLC, 2010 Load balancing nationallicence Price of anarchy nationallicence Price of stability nationallicence Congestion games nationallicence Online algorithms nationallicence Caragiannis Ioannis Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics, University of Patras, 26500, Rio, Greece aut Flammini Michele Dipartimento di Informatica, Università di L'Aquila, Via Vetoio, 67100, Coppito, L'Aquila, Italy aut Kaklamanis Christos Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics, University of Patras, 26500, Rio, Greece aut Kanellopoulos Panagiotis Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics, University of Patras, 26500, Rio, Greece aut Moscardelli Luca Department of Sciences, University of Chieti-Pescara, Viale Pindaro 42, 65127, Pescara, Italy aut Algorithmica Springer-Verlag 61/3(2011-11-01), 606-637 0178-4617 61:3<606 2011 61 453 https://doi.org/10.1007/s00453-010-9427-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9427-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Caragiannis Ioannis Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics, University of Patras, 26500, Rio, Greece aut NATIONALLICENCE 700 1- Flammini Michele Dipartimento di Informatica, Università di L'Aquila, Via Vetoio, 67100, Coppito, L'Aquila, Italy aut NATIONALLICENCE 700 1- Kaklamanis Christos Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics, University of Patras, 26500, Rio, Greece aut NATIONALLICENCE 700 1- Kanellopoulos Panagiotis Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics, University of Patras, 26500, Rio, Greece aut NATIONALLICENCE 700 1- Moscardelli Luca Department of Sciences, University of Chieti-Pescara, Viale Pindaro 42, 65127, Pescara, Italy aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/3(2011-11-01), 606-637 0178-4617 61:3<606 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer