Robust network optimization under polyhedral demand uncertainty is \(NP\)-hard
From MaRDI portal
Publication:968181
DOI10.1016/j.dam.2009.09.025zbMath1185.90213MaRDI 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
network flows; robust optimization; multicommodity flows; network optimization; polyhedral uncertainty
90C60: Abstract computational complexity for mathematical programming problems
90B10: Deterministic network models in operations research
90C27: Combinatorial optimization
Related Items
Tractable approximations to a robust capacity assignment model in telecommunications under demand uncertainty, Scenario based robust line balancing: Computational complexity, A comparison of routing sets for robust network design, On 2-stage robust LP with RHS uncertainty: complexity results and applications, Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard, The maximum flow problem of uncertain network, 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, Multi-service multi-facility network design under uncertainty, On the approximability of robust network design, Recent advances in robust optimization: an overview, The robust network loading problem with dynamic routing, A robust optimization model for distribution network design under a mixed integer set of scenarios, 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
