On the hardness of network design for bottleneck routing games

DOI10.1016/j.tcs.2013.11.035zbMath1310.91012DBLPjournals/tcs/FotakisKLS14OpenAlexW2788888306WikidataQ59818374 ScholiaQ59818374MaRDI QIDQ389953

Dimitris Fotakis, Alexis C. Kaporis, Paul G. Spirakis, Thanasis Lianeas

Publication date: 22 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.11.035

zbMATH Keywords

Braess's paradoxbottleneck routing gamesselfish network design

Mathematics Subject Classification ID

Noncooperative games (91A10) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Excluding Braess’s Paradox in Nonatomic Selfish Routing ⋮ Network characterizations for excluding Braess's paradox

Cites Work

• Unnamed Item
• Unnamed Item
• Atomic routing games on maximum congestion
• Network topology and the efficiency of equilibrium
• Efficient graph topologies in network routing games
• The directed subgraph homeomorphism problem
• On sparse approximations to randomized strategies and convex combinations
• On the severity of Braess's paradox: designing networks for selfish users is hard
• Simple strategies for large zero-sum games with applications to complexity theory
• Resolving Braess’s Paradox in Random Networks
• Bottleneck links, variable demand, and the tragedy of the commons
• Efficient Methods for Selfish Network Design
• The Hardness of Selective Network Design for Bottleneck Routing Games
• Über ein Paradoxon aus der Verkehrsplanung
• Automata, Languages and Programming
• Algorithms and Computation
• Approximation and Online Algorithms

This page was built for publication: On the hardness of network design for bottleneck routing games