A fully polynomial time approximation scheme for the probability maximizing shortest path problem

DOI10.1016/j.ejor.2021.10.018zbMath1495.90226OpenAlexW3207922128WikidataQ114184408 ScholiaQ114184408MaRDI QIDQ2670558

Jisun Lee, Kyungsik Lee, Seulgi Joung

Publication date: 11 March 2022

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

Full work available at URL: https://doi.org/10.1016/j.ejor.2021.10.018

zbMATH Keywords

shortest pathcombinatorial optimizationexact algorithmprobability maximizationfully polynomial time approximation scheme

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Stochastic programming (90C15) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• Robust optimization approach for a chance-constrained binary knapsack problem
• A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem
• Integer programming formulations for the elementary shortest path problem
• The constrained shortest path problem with stochastic correlated link travel times
• Maximum probability shortest path problem
• Multi-objective minmax robust combinatorial optimization with cardinality-constrained uncertainty
• The shortest path problem with two objective functions
• Stochastic spanning tree problem
• Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function
• Robust solutions of uncertain linear programs
• Algorithms and uncertainty sets for data-driven robust shortest path problems
• A minimum expected regret model for the shortest path problem with solution-dependent probability distributions
• Dynamic shortest path in stochastic dynamic networks: Ship routing problem
• Shortest paths algorithms: Theory and experimental evaluation
• The stochastic shortest path problem: a polyhedral combinatorics perspective
• Bi-criteria path problem with minimum length and maximum survival probability
• Maximum probabilistic all-or-nothing paths
• Wasserstein distributionally robust shortest path problem
• Applying Dijkstra's algorithm for general shortest path problem with normal probability distribution arc length
• On the Shortest Route Through a Network
• On a routing problem
• Faster algorithms for the shortest path problem
• An algorithm for the resource constrained shortest path problem
• The Stochastic Shortest Route Problem
• Reducibility among Combinatorial Problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• Computing a Most Probable Delay Constrained Path: NP-Hardness and Approximation Schemes
• Stochastic Shortest Paths Via Quasi-convex Maximization