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:
TitleEfficient Methods for Sel fish Network Design
Bibtex cite IDRACTI-RU1-2009-16
Year published 2009
Pages 1-12
Intuitively, Braess's paradox states that destroying a part of a network may improve the common latency of sel sh ows at Nash equilibrium. Such a paradox is a pervasive phenomenon in real-world networks. Any administrator, who wants to improve equilibrium delays in sel sh networks, is facing some basic questions: (i) Is the network paradox-ridden? (ii) How can we delete some edges to optimize equilibrium ow delays? (iii) How can we modify edge latencies to optimize equilibrium ow delays? Unfortunately, such questions lead to NP-hard problems in general. In this work, we impose some natural restrictions on our networks, e.g. we assume strictly increasing linear latencies. Our target is to formulate ecient algorithms for the three questions above.We manage to provide: A polynomial-time algorithm that decides if a network is paradoxridden, when latencies are linear and strictly increasing. A reduction of the problem of deciding if a network with arbitrary linear latencies is paradox-ridden to the problem of generating all optimal basic feasible solutions of a Linear Program that describes the optimal trac allocations to the edges with constant latency. An algorithm for nding a subnetwork that is almost optimal wrt equilibrium latency. Our algorithm is subexponential when the number of paths is polynomial and each path is of polylogarithmic length. A polynomial-time algorithm for the problem of nding the best subnetwork, which outperforms any known approximation algorithm for the case of strictly increasing linear latencies. A polynomial-time method that turns the optimal ow into a Nash ow by deleting the edges not used by the optimal ow, and performing minimal modi cations to the latencies of the remaining ones. Our results provide a deeper understanding of the computational complexity of recognizing the Braess's paradox most severe manifestations, and our techniques show novel ways of using the probabilistic method and of exploiting convex separable quadratic programs.
Fotakis, Dimitris
Kaporis, Alexis
Spirakis, Paul
icalp09c_42.pdf (main file)
Publication ID657