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

DOI10.1016/S0377-2217(03)00373-4zbMATH Open1056.90125MaRDI QIDQ596264FDOQ596264

Paweł Zieliński

Publication date: 10 August 2004

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

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

zbMATH Keywords

Computational complexityCombinatorial optimizationInterval dataRobust optimizationShortest path problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Robust Optimization of Large-Scale Systems
• Robust discrete optimization and its applications
• On the robust shortest path problem.
• An exact algorithm for the robust shortest path problem with interval data
• On the complexity of a class of combinatorial optimization problems with uncertainty
• The robust spanning tree problem with interval data

Cited In (36)

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

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)