Complexity and Approximation of the Continuous Network Design Problem

DOI10.1137/15M1016461zbMath1376.90068OpenAlexW3021232757MaRDI QIDQ5348461

Martin Gairing, Tobias Harks, Max Klimm

Publication date: 16 August 2017

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitynetwork designapproximation algorithmsbilevel optimizationwardrop equilibriumoptimization under equilibrium constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items (4)

A Unified Framework for Pricing in Nonconvex Resource Allocation Games ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ Stackelberg pricing games with congestion effects ⋮ A tri-level optimization model for a private road competition problem with traffic equilibrium constraints

Cites Work

• Unnamed Item
• Efficient implementation of heuristics for the continuous network design problem
• An efficient dual approach to the urban road network design problem
• Geometric algorithms and combinatorial optimization.
• An overview of bilevel optimization
• On the severity of Braess's paradox: designing networks for selfish users is hard
• Complexity and Approximation of the Continuous Network Design Problem
• How bad is selfish routing?
• Stronger Bounds on Braess's Paradox and the Maximum Latency of Selfish Routing
• Inefficiency of Nash Equilibria
• Network design problem with congestion effects: A case of bilevel programming
• Avoiding the Braess paradox in non-cooperative networks
• Network Improvement for Equilibrium Routing
• Über ein Paradoxon aus der Verkehrsplanung
• Selfish Routing in Capacitated Networks
• Mathematical Programs with Equilibrium Constraints
• The price of anarchy is independent of the network topology

This page was built for publication: Complexity and Approximation of the Continuous Network Design Problem