Article ID Journal Published Year Pages File Type
1142032 Operations Research Letters 2016 4 Pages PDF
Abstract
In this paper we study the inefficiency ratio of stable equilibria in load balancing games introduced by Asadpour and Saberi (2009). We prove tighter lower and upper bounds of 7/6 and 4/3, respectively. This improves over the best known bounds for the 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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,