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

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

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

Abstract

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
http://link.springer.com/chapter/10.1007%2F978-3-319-07557-0_12PublisherArticle
http://www.or.uni-bonn.de/ipco/OrganizationConference Website
ORCID:
AuthorORCID
Ligett, Katrina0000-0003-2780-6656
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.
Funders:
Funding AgencyGrant Number
NSF1038578
NSF1319745
NSF1254169
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:https://resolver.caltech.edu/CaltechAUTHORS:20150223-101614687
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:55095
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:23 Feb 2015 19:41
Last Modified:03 Oct 2019 08:03

Repository Staff Only: item control page