Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142032 | Operations Research Letters | 2016 | 4 Pages |
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
Akaki Mamageishvili, Paolo Penna,