The computational complexity of the relative robust shortest path problem with interval data
From MaRDI portal
Publication:596264
DOI10.1016/S0377-2217(03)00373-4zbMath1056.90125MaRDI QIDQ596264
Publication date: 10 August 2004
Published in: European Journal of Operational Research (Search for Journal in Brave)
Combinatorial optimizationComputational complexityInterval dataRobust optimizationShortest path problem
Related Items (34)
A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs ⋮ Optimization under Decision-Dependent Uncertainty ⋮ New models for the robust shortest path problem: complexity, resolution and generalization ⋮ Shortest paths with shortest detours. A biobjective routing problem ⋮ Restricted robust uniform matroid maximization under interval uncertainty ⋮ Minimax regret spanning arborescences under uncertain costs ⋮ An approach to the distributionally robust shortest path problem ⋮ A robust optimization model for distribution network design under a mixed integer set of scenarios ⋮ How much the grid network and rescuers' communication can improve the rescue efficiency in worst-case analysis ⋮ Risk models for the prize collecting Steiner tree problems with interval data ⋮ Robust Algorithms for TSP and Steiner Tree ⋮ Deterministic risk control for cost-effective network connections ⋮ The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows ⋮ Algorithms for the minmax regret path problem with interval data ⋮ Minmax regret bottleneck problems with solution-induced interval uncertainty structure ⋮ Maximizing the configuration robustness for parallel multi-purpose machines under setup cost constraints ⋮ On a constant factor approximation for minmax regret problems using a symmetry point scenario ⋮ A branch and bound algorithm for the robust shortest path problem with interval data. ⋮ On a Class of Interval Data Minmax Regret CO Problems ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty ⋮ An \(s\)-\(t\) connection problem with adaptability ⋮ On the approximability of minmax (regret) network optimization problems ⋮ Reduction approaches for robust shortest path problems ⋮ A Benders decomposition approach for the robust spanning tree problem with interval data ⋮ A 2-approximation for minmax regret problems via a mid-point scenario optimal solution ⋮ A new model for path planning with interval data ⋮ A minmax regret approach to the critical path method with task interval times ⋮ Computing and minimizing the relative regret in combinatorial optimization with interval data ⋮ The most likely path on series-parallel networks ⋮ An approximation algorithm for interval data minmax regret combinatorial optimization problems ⋮ Improved polynomial algorithms for robust bottleneck problems with interval data ⋮ The robust shortest path problem in series -- parallel multidigraphs with interval data ⋮ Robust Optimization for the Hazardous Materials Transportation Network Design Problem ⋮ Robust optimization for the hazardous materials transportation network design problem
Cites Work
- Robust discrete optimization and its applications
- On the robust shortest path problem.
- An exact algorithm for the robust shortest path problem with interval data
- Robust Optimization of Large-Scale Systems
- On the complexity of a class of combinatorial optimization problems with uncertainty
- The robust spanning tree problem with interval data
- Unnamed Item
This page was built for publication: The computational complexity of the relative robust shortest path problem with interval data
