A Caltech Library Service

Network Improvement for Equilibrium Routing

Bhaskar, Umang and Ligett, Katrina and Schulman, Leonard J. (2014) Network Improvement for Equilibrium Routing. In: Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science. No.8494. Springer , Cham, Switzerland, pp. 138-149. ISBN 978-3-319-07556-3.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


In routing games, agents pick routes through a network to minimize their own delay. A primary concern for the network designer in routing games is the average agent delay at equilibrium. A number of methods to control this average delay have received substantial attention, including network tolls, Stackelberg routing, and edge removal. A related approach with arguably greater practical relevance is that of making investments in improvements to the edges of the network, so that, for a given investment budget, the average delay at equilibrium in the improved network is minimized. This problem has received considerable attention in the literature on transportation research. We study a model for this problem introduced in transportation research literature, and present both hardness results and algorithms that obtain tight performance guarantees. – In general graphs, we show that a simple algorithm obtains a 4/3-approximation for affine delay functions and an O(p/ log p)- approximation for polynomial delay functions of degree p. For affine delays, we show that it is NP-hard to improve upon the 4/3 approximation. – Motivated by the practical relevance of the problem, we consider restricted topologies to obtain better bounds. In series-parallel graphs, we show that the problem is still NP-hard. However, we show that there is an FPTAS in this case. – Finally, for graphs consisting of parallel paths, we show that an optimal allocation can be obtained in polynomial time.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Website ReadCube access
Ligett, Katrina0000-0003-2780-6656
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2014 Springer International Publishing Switzerland. Supported in part by NSF Awards 1038578 and 1319745, an NSF CAREER Award (1254169), the Charles Lee Powell Foundation, and a Microsoft Research Faculty Fellowship.
Funding AgencyGrant Number
Charles Lee Powell FoundationUNSPECIFIED
Microsoft Research Faculty FellowshipUNSPECIFIED
Series Name:Lecture Notes in Computer Science
Issue or Number:8494
Record Number:CaltechAUTHORS:20150223-101614687
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:55095
Deposited By: Tony Diaz
Deposited On:23 Feb 2015 19:41
Last Modified:29 Apr 2020 19:50

Repository Staff Only: item control page