Optimization algorithms for energy-efficient data centers
Hendrik F. Hamann
InterPACK 2013
In this paper we study the "price of anarchy" for the general class of (weighted and unweighted) atomic "congestion games" with the sum of players' costs as the objective function. We show that for linear resource cost functions the price of anarchy is exactly 3+ √5/2 ≈ 2.618 for weighted congestion games and exactly 2.5 for unweighted congestion games. We show that for resource cost functions that are polynomials of degree d the price of anarchy is dΘ(d). Our results also hold for mixed strategies. In particular, these results apply to atomic routing games where the traffic demand from a source to a destination must be satisfied by choosing a single path between source and destination. © 2013 Society for Industrial and Applied Mathematics.
Hendrik F. Hamann
InterPACK 2013
Minkyong Kim, Zhen Liu, et al.
INFOCOM 2008
Pradip Bose
VTS 1998
Nanda Kambhatla
ACL 2004