Name
Abstract | ||
|---|---|---|
In routing games, agents pick their 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 and a number of different algorithms have been studied. To our knowledge, none of this work gives guarantees on the output quality of any polynomial-time algorithm. We study a model for this problem introduced in transportation research literature, and present both hardness results and algorithms that obtain nearly optimal performance guarantees. - We first show that a simple algorithm obtains good approximation guarantees for the problem. Despite its simplicity, we show that for affine delays the approximation ratio of 4/3 obtained by the algorithm cannot be improved. - To obtain better results, we then consider restricted topologies. For graphs consisting of parallel paths with affine delay functions we give an optimal algorithm. However, for graphs that consist of a series of parallel links, we show the problem is weakly NP-hard. - Finally, we consider the problem in series-parallel graphs, and give an FPTAS for this case. Our work thus formalizes the intuition held by transportation researchers that the network improvement problem is hard, and presents topology-dependent algorithms that have provably tight approximation guarantees. |
Year | Venue | Field |
|---|---|---|
2013 | CoRR | Affine transformation,Graph,Mathematical economics,Mathematical optimization,Network delay,Intuition,Network topology,SIMPLE algorithm,Stackelberg competition,Mathematics |
DocType | Volume | Citations |
Journal | abs/1307.3794 | 2 |
PageRank | References | Authors |
0.39 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Umang Bhaskar | 1 | 67 | 11.75 |
| Katrina Ligett | 2 | 923 | 66.19 |
| Leonard J. Schulman | 3 | 1328 | 136.88 |