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

DOI10.1016/J.EJOR.2021.10.018MaRDI QIDQ2670558zbMATH OpenOpenAlexWikidataFDO

Authors J. S. Lee, Seulgi Joung, Kyungsik Lee

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

combinatorial optimizationexact algorithmfully polynomial time approximation schemeprobability maximizationshortest path

Mathematics Subject Classification ID

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

Recommendations

• Maximum probability shortest path problem
• Bi-criteria path problem with minimum length and maximum survival probability
• Stochastic Shortest Paths Via Quasi-convex Maximization
• Shortest path problems with node failures
• Publication:4726020

Cites work

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

Cited in

(6)

• Bi-criteria path problem with minimum length and maximum survival probability
• Maximum probabilistic all-or-nothing paths
• Polynomial-time approximation schemes for shortest path with alternatives
• The probabilistic longest path problem
• Maximum probability shortest path problem
• Stochastic Shortest Paths Via Quasi-convex Maximization

This page was built for publication: A fully polynomial time approximation scheme for the probability maximizing shortest path problem

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