Network Improvement for Equilibrium Routing

DOI10.1007/978-3-319-07557-0_12MaRDI QIDQ5418991zbMATH OpenOpenAlexFDO

Authors Umang Bhaskar, Katrina Ligett, Leonard J. Schulman

Publication date 2 June 2014

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.3794, https://resolver.caltech.edu/CaltechAUTHORS:20150220-135314566

zbMATH Keywords

network improvementpolynomial delay functionsrouting gamestransportation research

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Games involving graphs (91A43)

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.

Recommendations

• Equilibrium routing strategies in data transmission networks
• On equilibrium routing in data-transmission networks
• Equilibrium routing of ring networks
• The existence of equilibrium routing in networks of data transmission
• scientific article; zbMATH DE number 3982887
• Optimization of dynamic routing networks
• Equilibrium routing under uncertainty
• Improved efficient routing strategy on scale-free networks
• A selfish routing based network improvement problem

Cited in

(5)

• Achieving target equilibria in network routing games without knowing the latency functions
• scientific article; zbMATH DE number 3982887 (Why is no real title available?)
• Complexity and approximation of the continuous network design problem
• A selfish routing based network improvement problem
• Improving Topological Routing in N2R Networks

This page was built for publication: Network Improvement for Equilibrium Routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5418991)