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: |
| ||||||||||||
ORCID: |
| ||||||||||||
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: |
| ||||||||||||
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: | 29 Apr 2020 19:50 |
Repository Staff Only: item control page