CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20150220-135314566

[img] PDF - Submitted Version
See Usage Policy.

251Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20150220-135314566

Abstract

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
http://dx.doi.org/10.1145/2728732.2728737DOIArticle
http://dl.acm.org/citation.cfm?doid=2728732.2728737PublisherArticle
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
NSF1254169
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:https://resolver.caltech.edu/CaltechAUTHORS:20150220-135314566
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:55068
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:23 Feb 2015 20:04
Last Modified:03 Oct 2019 08:02

Repository Staff Only: item control page