Tighter Bounds on the Inefficiency Ratio of Stable Equilibria in Load Balancing Games
METADATA ONLY
Loading...
Author / Producer
Date
2015-12-10
Publication Type
Working Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
In this paper we study the inefficiency ratio of stable equilibria in load balancing games introduced by Asadpour and Saberi [3]. 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
Pages / Article No.
1512.03484
Publisher
Cornell University
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
Notes
Funding
143323 - Network-Creation and Network-Design Games (SNF)
Related publications and datasets
Is previous version of: