On the hardness of network design for bottleneck routing games
DOI10.1016/J.TCS.2013.11.035zbMATH Open1310.91012DBLPjournals/tcs/FotakisKLS14OpenAlexW2788888306WikidataQ59818374 ScholiaQ59818374MaRDI QIDQ389953FDOQ389953
Authors: Dimitris Fotakis, A. C. Kaporis, Thanasis Lianeas, P. G. Spirakis 
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
Recommendations
- On the hardness of network design for bottleneck routing games
- On the severity of Braess's paradox: designing networks for selfish users is hard
- Efficient Methods for Selfish Network Design
- Efficient methods for selfish network design
- The Hardness of Selective Network Design for Bottleneck Routing Games
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) Games involving graphs (91A43)
Cites Work
- Worst-case equilibria
- On the severity of Braess's paradox: designing networks for selfish users is hard
- Über ein Paradoxon aus der Verkehrsplanung
- The directed subgraph homeomorphism problem
- Simple strategies for large zero-sum games with applications to complexity theory
- Efficient graph topologies in network routing games
- Algorithms and Computation
- Atomic routing games on maximum congestion
- Network topology and the efficiency of equilibrium
- Title not available (Why is that?)
- Bottleneck links, variable demand, and the tragedy of the commons
- On sparse approximations to randomized strategies and convex combinations
- Resolving Braess's paradox in random networks
- Efficient Methods for Selfish Network Design
- The Hardness of Selective Network Design for Bottleneck Routing Games
- Automata, Languages and Programming
- Approximation and Online Algorithms
Cited In (12)
- \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games
- The Hardness of Selective Network Design for Bottleneck Routing Games
- Stronger bounds on Braess's paradox and the maximum latency of selfish routing
- Excluding Braess's paradox in nonatomic selfish routing
- Efficient methods for selfish network design
- On the severity of Braess's paradox: designing networks for selfish users is hard
- Approximation and Online Algorithms
- Automata, Languages and Programming
- Network characterizations for excluding Braess's paradox
- On the core of routing games
- On the hardness of network design for bottleneck routing games
- Efficient Methods for Selfish Network Design
This page was built for publication: On the hardness of network design for bottleneck routing games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q389953)
