Stochastic Shortest Paths Via Quasi-convex Maximization

DOI10.1007/11841036_50MaRDI QIDQ5449558zbMATH OpenOpenAlexFDO

Authors E. Nikolova, Jonathan Kelner, Matthew Brand, Michael Mitzenmacher

Publication date 11 March 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11841036_50

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Maximum probability shortest path problem
• A fully polynomial time approximation scheme for the probability maximizing shortest path problem
• Variations on the stochastic shortest path problem
• On Shortest Paths in Graphs with Random Weights
• Stochastic shortest path problems with recourse

Cited in

(36)

• A traveling salesman problem with pickups and deliveries and stochastic travel times: an application from chemical shipping
• A fully polynomial-time approximation scheme for approximating a sum of random variables
• Distributionally robust maximum probability shortest path problem
• An approximation algorithm for a general class of multi-parametric optimization problems
• An approximation algorithm for a general class of parametric optimization problems
• Joint chance constrained shortest path problem with Copula theory
• Dynamic journeying under uncertainty
• Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra
• Wasserstein distributionally robust shortest path problem
• Equilibrium routing under uncertainty
• Algorithms for non-linear and stochastic resource constrained shortest path
• Finding reliable shortest paths in road networks under uncertainty
• A multi-objective approach for PH-graphs with applications to stochastic shortest paths
• A fully polynomial time approximation scheme for the probability maximizing shortest path problem
• Routing optimization under uncertainty
• Additive consistency of risk measures and its application to risk-averse routing in networks
• A mean-risk model for the traffic assignment problem with stochastic travel times
• Approximation algorithms for stochastic combinatorial optimization problems
• New reformulations of distributionally robust shortest path problem
• A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems
• Technical Note—A Note on the Stochastic Shortest Route Problem
• Possibilistic bottleneck combinatorial optimization problems with ill-known weights
• On the complexity of time-dependent shortest paths
• Maximum probability shortest path problem
• Constrained shortest path with uncertain transit times
• Robust adaptive routing under uncertainty
• Computing constrained shortest-paths at scale
• Parametric computation of minimum-cost flows with piecewise quadratic costs
• Submodularity in Conic Quadratic Mixed 0–1 Optimization
• Risk-averse selfish routing
• Maximizing expected utility for stochastic combinatorial optimization problems
• The Value of Side Information in Shortest Path Optimization
• Energy of convex sets, shortest paths, and resistance
• Parametric matroid interdiction
• A survey of exact and approximation algorithms for linear-parametric optimization problems
• Stochastic shortest path with unlimited hops

This page was built for publication: Stochastic Shortest Paths Via Quasi-convex Maximization

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