Robust network optimization under polyhedral demand uncertainty is \(NP\)-hard
From MaRDI portal
Publication:968181
DOI10.1016/j.dam.2009.09.025zbMath1185.90213OpenAlexW2134200749MaRDI QIDQ968181
Publication date: 5 May 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2009.09.025
Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)
Related Items
The robust network loading problem with dynamic routing ⋮ Tractable approximations to a robust capacity assignment model in telecommunications under demand uncertainty ⋮ A robust optimization model for distribution network design under a mixed integer set of scenarios ⋮ On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows ⋮ Affine routing for robust network design ⋮ On 2-stage robust LP with RHS uncertainty: complexity results and applications ⋮ The maximum flow problem of uncertain network ⋮ Scenario based robust line balancing: Computational complexity ⋮ A comparison of routing sets for robust network design ⋮ Multipolar robust optimization ⋮ \(k\)-adaptive routing for the robust network loading problem ⋮ A comparison of different routing schemes for the robust network loading problem: polyhedral results and computation ⋮ On the approximability of robust network design ⋮ Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard ⋮ Recent advances in robust optimization: an overview ⋮ Multi-service multi-facility network design under uncertainty ⋮ Robust capacity assignment solutions for telecommunications networks with uncertain demands
Cites Work
- Unnamed Item
- On 2-stage robust LP with RHS uncertainty: complexity results and applications
- A theorem on flows in networks
- Routing of uncertain traffic demands
- On robust maximum flow with polyhedral uncertainty sets
- Combinatorial approaches to multiflow problems
- Partitioning procedures for solving mixed-variables programming problems
- The ellipsoid method and its consequences in combinatorial optimization
- A robustness approach to uncapacitated network design problems
- Robust solutions of uncertain linear programs
- Robust discrete optimization and its applications
- Robust discrete optimization and network flows
- Discrete cost multicommodity network optimization problems and exact solution methods
- Robust optimization-methodology and applications
- Applying Robust Optimization to Capacity Expansion of One Location in Telecommunications with Demand Uncertainty
- Two-Stage Robust Network Flow and Design Under Demand Uncertainty
- An approach to robust network design in telecommunications
- The Price of Robustness
- On the Existence of a Feasible Flow in a Stochastic Transportation Network
- Two-Processor Scheduling with Start-Times and Deadlines
- Robust Optimization for Power Systems Capacity Expansion under Uncertainty
- Robust capacity expansion of network flows
