A Caltech Library Service

Network improvement for equilibrium routing

Bhaskar, Umang and Ligett, Katrina (2014) Network improvement for equilibrium routing. ACM SIGecom Exchanges, 13 (2). pp. 36-40. ISSN 1551-9031.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Routing games are frequently used to model the behavior of traffic in large networks, such as road networks. In transportation research, the problem of adding capacity to a road network in a cost-effective manner to minimize the total delay at equilibrium is known as the Network Design Problem, and has received considerable attention. However, prior to our work, little was known about guarantees for polynomial-time algorithms for this problem. We obtain tight approximation guarantees for general and series-parallel networks, and present a number of open questions for future work.

Item Type:Article
Related URLs:
URLURL TypeDescription
Ligett, Katrina0000-0003-2780-6656
Alternate Title:The Network Improvement Problem for Equilibrium Routing
Additional Information:© 2015 ACM, Inc. K. Ligett gratefully acknowledges support of 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
Subject Keywords:Algorithms; Theory; Economics; Routing games; Network design; Wardrop equilibrium
Issue or Number:2
Record Number:CaltechAUTHORS:20150220-135314566
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:55068
Deposited By: Tony Diaz
Deposited On:23 Feb 2015 20:04
Last Modified:03 Oct 2019 08:02

Repository Staff Only: item control page