research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleResolving Braess's Paradox in Random Networks
Bibtex cite IDRACTI-RU1-2013-46
Booktitle WINE 2013
Year published 2013
Location USA
Braessís paradox states that removing a part of a network may im- prove the playersí latency at equilibrium. In this work, we study the approxima- bility of the best subnetwork problem for the class of random G n;p instances proven prone to Braessís paradox by (Roughgarden and Valiant, RSA 2010) and (Chung and Young, WINE 2010). Our main contribution is a polynomial-time approximation-preserving reduction of the best subnetwork problem for such in- stances to the corresponding problem in a simplified network where all neighbors of s and t are directly connected by 0 latency edges. Building on this, we obtain an approximation scheme that for any constant " > 0 and with high probabil- ity, computes a subnetwork and an " -Nash flow with maximum latency at most (1+ " ) L + " , where L is the equilibrium latency of the best subnetwork. Our ap- proximation scheme runs in polynomial time if the random network has average degree O (poly(ln n )) and the traffic rate is O (poly(lnln n )) , and in quasipoly- nomial time for average degrees up to o ( n ) and traffic rates of O (poly(ln n )) .
Fotakis, Dimitris
Kaporis, Alexis
Lianeas, Thanasis
Spirakis, Paul
Publication ID1041