Stochastic Shortest Paths Via Quasi-convex Maximization

DOI10.1007/11841036_50zbMath1131.05317OpenAlexW2122967662MaRDI QIDQ5449558

Evdokia Nikolova, Matthew Brand, Jonathan A. Kelner, 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

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

Related Items (30)

Finding reliable shortest paths in road networks under uncertainty ⋮ Distance oracles for time-dependent networks ⋮ Approximation algorithms for stochastic combinatorial optimization problems ⋮ An approximation algorithm for a general class of parametric optimization problems ⋮ New reformulations of distributionally robust shortest path problem ⋮ Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs ⋮ A fully polynomial time approximation scheme for the probability maximizing shortest path problem ⋮ Joint chance constrained shortest path problem with Copula theory ⋮ Algorithms for non-linear and stochastic resource constrained shortest path ⋮ Parametric matroid interdiction ⋮ Possibilistic bottleneck combinatorial optimization problems with ill-known weights ⋮ Submodularity in Conic Quadratic Mixed 0–1 Optimization ⋮ On the complexity of time-dependent shortest paths ⋮ Maximum probability shortest path problem ⋮ Constrained shortest path with uncertain transit times ⋮ A traveling salesman problem with pickups and deliveries and stochastic travel times: an application from chemical shipping ⋮ Dynamic journeying under uncertainty ⋮ Stochastic shortest path with unlimited hops ⋮ A fully polynomial-time approximation scheme for approximating a sum of random variables ⋮ Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra ⋮ Routing Optimization Under Uncertainty ⋮ Robust Adaptive Routing Under Uncertainty ⋮ Risk-Averse Selfish Routing ⋮ Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems ⋮ Additive Consistency of Risk Measures and Its Application to Risk-Averse Routing in Networks ⋮ Distributionally robust maximum probability shortest path problem ⋮ An approximation algorithm for a general class of multi-parametric optimization problems ⋮ Equilibrium routing under uncertainty ⋮ A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times ⋮ Computing Constrained Shortest-Paths at Scale

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