Stronger Bounds on Braess's Paradox and the Maximum Latency of Selfish Routing

DOI10.1137/090769600zbMath1234.68155OpenAlexW2135149577MaRDI QIDQ3225146

Asher Walkover, Tim Roughgarden, Henry W. Lin, Éva Tardos

Publication date: 15 March 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090769600

zbMATH Keywords

approximation algorithmsprice of anarchytraffic networksselfish routingBraess's paradox

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Communication networks in operations research (90B18) Traffic problems in operations research (90B20) Approximation algorithms (68W25)

Related Items (15)

Excluding Braess’s Paradox in Nonatomic Selfish Routing ⋮ Dynamics of a 2D Piecewise Linear Braess Paradox Model: Effect of the Third Partition ⋮ Collusion in atomic splittable routing games ⋮ Resolving Braess's paradox in random networks ⋮ Complexity and Approximation of the Continuous Network Design Problem ⋮ Price of Anarchy in Networks with Heterogeneous Latency Functions ⋮ Stability vs. optimality in selfish ring routing ⋮ The impact of worst-case deviations in non-atomic network routing games ⋮ A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs ⋮ Network characterizations for excluding Braess's paradox ⋮ Magnitude of inefficiency ⋮ Informational Braess’ Paradox: The Effect of Information on Traffic Congestion ⋮ The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games ⋮ Load balancing congestion games and their asymptotic behavior ⋮ Network Pricing: How to Induce Optimal Flows Under Strategic Link Operators

This page was built for publication: Stronger Bounds on Braess's Paradox and the Maximum Latency of Selfish Routing