The computational complexity of the relative robust shortest path problem with interval data

DOI10.1016/S0377-2217(03)00373-4MaRDI QIDQ596264zbMATH OpenFDO

Authors Paweł Zieliński

Publication date 10 August 2004

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0377-2217(03)00373-4

zbMATH Keywords

Combinatorial optimizationComputational complexityInterval dataRobust optimizationShortest path problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• An exact algorithm for the robust shortest path problem with interval data
• A branch and bound algorithm for the robust shortest path problem with interval data.
• The robust shortest path problem with interval data via Benders decomposition
• New models for the robust shortest path problem: complexity, resolution and generalization
• The robust shortest path problem in series -- parallel multidigraphs with interval data
• The rough interval shortest path problem
• On the robust shortest path problem.
• An enhanced exact procedure for the absolute robust shortest path problem
• Robust shortest path problems
• Algorithms and uncertainty sets for data-driven robust shortest path problems

Cites work

• An exact algorithm for the robust shortest path problem with interval data
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the complexity of a class of combinatorial optimization problems with uncertainty
• On the robust shortest path problem.
• Robust discrete optimization and its applications
• Robust Optimization of Large-Scale Systems
• The robust spanning tree problem with interval data

Cited in

(39)

• 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
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Improved polynomial algorithms for robust bottleneck problems with interval data
• A branch and bound algorithm for the robust shortest path problem with interval data.
• On the complexity of the robust spanning tree problem with interval data
• A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
• Shortest paths with shortest detours. A biobjective routing problem
• An exact algorithm for the robust shortest path problem with interval data
• Complexity of the robust weighted independent set problems on interval graphs
• Algorithms for the minmax regret path problem with interval data
• Combinatorial two-stage minmax regret problems under interval uncertainty
• Robust optimization for the hazardous materials transportation network design problem
• Maximizing the configuration robustness for parallel multi-purpose machines under setup cost constraints
• A Benders decomposition approach for the robust spanning tree problem with interval data
• The robust shortest path problem in series -- parallel multidigraphs with interval data
• An approach to the distributionally robust shortest path problem
• A robust optimization model for distribution network design under a mixed integer set of scenarios
• Robust optimization for the hazardous materials transportation network design problem
• The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows
• The most likely path on series-parallel networks
• New models for the robust shortest path problem: complexity, resolution and generalization
• Risk models for the prize collecting Steiner tree problems with interval data
• Minmax regret bottleneck problems with solution-induced interval uncertainty structure
• On a constant factor approximation for minmax regret problems using a symmetry point scenario
• Optimization under decision-dependent uncertainty
• An s-t connection problem with adaptability
• On a Class of Interval Data Minmax Regret CO Problems
• Robust Algorithms for TSP and Steiner Tree
• Deterministic risk control for cost-effective network connections
• Robust algorithms for TSP and Steiner tree
• Robust and distributionally robust shortest path problems: a survey
• Reduction approaches for robust shortest path problems
• Restricted robust uniform matroid maximization under interval uncertainty
• Minimax regret spanning arborescences under uncertain costs
• How much the grid network and rescuers' communication can improve the rescue efficiency in worst-case analysis
• On the approximability of minmax (regret) network optimization problems
• A 2-approximation for minmax regret problems via a mid-point scenario optimal solution

This page was built for publication: The computational complexity of the relative robust shortest path problem with interval data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q596264)