Approximating the shortest path problem with scenarios

DOI10.1016/J.TCS.2024.114972MaRDI QIDQ6652474zbMATH OpenFDO

Authors Adam Kasperski, Paweł Zieliński

Publication date 12 December 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114972

zbMATH Keywords

approximation algorithmcombinatorial optimizationrobust optimizationshortest path problemuncertainty

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• Algorithms – ESA 2005
• Approximation of min-max and min-max regret versions of some combinatorial optimization problems
• General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems
• A simple efficient approximation scheme for the restricted shortest path problem

Cites work

• A faster algorithm for solving general LPs
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• A survey and annotated bibliography of multiobjective combinatorial optimization
• Approximability of the robust representatives selection problem
• Approximation of min-max and min-max regret versions of some combinatorial optimization problems
• Complexity and in-approximability of a selection problem in robust optimization
• scientific article; zbMATH DE number 663895 (Why is no real title available?)
• Min-max and min-max (relative) regret approaches to representatives selection problem
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Multi‐objective combinatorial optimization problems: A survey
• Multicriteria Optimization
• Network flows. Theory, algorithms, and applications.
• New approaches to multi-objective optimization
• On the approximability of minmax (regret) network optimization problems
• On the robust shortest path problem.
• Recoverable robust shortest path problems
• Robust discrete optimization and its applications
• Robust optimization
• Scenarios and Policy Aggregation in Optimization Under Uncertainty
• Simple greedy algorithms for fundamental multidimensional graph problems
• The concept of recoverable robustness, linear programming recovery, and railway applications
• The Recognition of Series Parallel Digraphs

This page was built for publication: Approximating the shortest path problem with scenarios

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