Tighter Bounds on the Inefficiency Ratio of Stable Equilibria in Load Balancing Games
- Working Paper
In this paper we study the inefficiency ratio of stable equilibria in load balancing games introduced by Asadpour and Saberi . We prove tighter lower and upper bounds of 7/6 and 4/3, respectively. This improves over the best known bounds in problem (19/18 and 3/2, respectively). Equivalently, the results apply to the question of how well the optimum for the L2 -norm can approximate the L∞-norm (makespan) in identical machines scheduling Show more
Journal / seriesarXiv
Organisational unit03340 - Widmayer, Peter
NotesSubmitted on 10 December 2015. See also: http://e-citations.ethbib.ethz.ch/view/pub:181325.
MoreShow all metadata