Selfish splittable flows and NP-completeness

DOI10.1016/j.cosrev.2011.04.002zbMath1298.68055OpenAlexW1973957391MaRDI QIDQ465681

Alexis C. Kaporis, Paul G. Spirakis

Publication date: 24 October 2014

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

Full work available at URL: https://doi.org/10.1016/j.cosrev.2011.04.002

zbMATH Keywords

selfish routingBraess's paradoxnetwork performanceAlthoefer's sparsification lemma

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Efficient methods for selfish network design ⋮ The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial algorithm for minimum quadratic cost flow problems
• Network topology and the efficiency of equilibrium
• Uniqueness of solution in linear programming
• On sparse approximations to randomized strategies and convex combinations
• Complexity and algorithms for nonlinear optimization problems
• On the severity of Braess's paradox: designing networks for selfish users is hard
• Braess's Paradox in large random graphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• The complexity of pure Nash equilibria
• The Prevalence of Paradoxes in Transportation Equilibrium Problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• P-Complete Approximation Problems
• Algorithms, games, and the internet
• Efficient Methods for Selfish Network Design
• Probability Inequalities for Sums of Bounded Random Variables
• Algorithmic Game Theory
• Über ein Paradoxon aus der Verkehrsplanung
• Traffic assignment problem for a general network
• Convex separable optimization is not much harder than linear optimization
• Nonlinear networks. IIa

This page was built for publication: Selfish splittable flows and NP-completeness