Recoverable robust shortest path problems

DOI10.1002/net.20487zbMath1241.90016OpenAlexW2034844194MaRDI QIDQ2892155

Christina Büsing

Publication date: 18 June 2012

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20487

zbMATH Keywords

robustnessapproximationuncertaintiesNP-hardnessshortest path problemrecovery

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items (19)

The recoverable robust spanning tree problem with interval costs is polynomially solvable ⋮ Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty ⋮ Investigating the recoverable robust single machine scheduling problem under interval uncertainty ⋮ Algorithms and uncertainty sets for data-driven robust shortest path problems ⋮ Decomposition approaches for recoverable robust optimization problems ⋮ On the recoverable robust traveling salesman problem ⋮ Designing and constructing networks under uncertainty in the construction stage: definition and exact algorithmic approach ⋮ A parameterized view to the robust recoverable base problem of matroids under structural uncertainty ⋮ Recoverable robust representatives selection problems with discrete budgeted uncertainty ⋮ Recoverable robust spanning tree problem under interval uncertainty representations ⋮ Robust recoverable and two-stage selection problems ⋮ On recoverable and two-stage robust selection problems with budgeted uncertainty ⋮ Robust recoverable 0-1 optimization problems under polyhedral uncertainty ⋮ Minimizing recovery cost of network optimization problems ⋮ On the complexity of robust multi-stage problems with discrete recourse ⋮ Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints ⋮ Robust combinatorial optimization under convex and discrete cost uncertainty ⋮ A linear time algorithm for the robust recoverable selection problem ⋮ Min-max-min robust combinatorial optimization

Cites Work

• On the approximability of minmax (regret) network optimization problems
• The directed subgraph homeomorphism problem
• On the robust shortest path problem.
• Robust discrete optimization and network flows
• Adjustable robust solutions of uncertain linear programs
• The robust shortest path problem with interval data via Benders decomposition
• The robust shortest path problem in series -- parallel multidigraphs with interval data
• The Price of Robustness
• The Concept of Recoverable Robustness, Linear Programming Recovery, and Railway Applications
• The Exact Subgraph Recoverable Robust Shortest Path Problem
• Shortest chain subject to side constraints
• A Polynomial Solution to the Undirected Two Paths Problem
• Robust Optimization of Large-Scale Systems
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Recoverable robust shortest path problems