Stochastic Shortest Paths Via Quasi-convex Maximization
| Citation: | Nikolova, E.; Kelner, J.; Brand, M.; Mitzenmacher,M., "Stochastic Shortest Paths Via Quasi-convex Maximization", ESA 2006, ISBN:3-540-38875-3, Pp 552 - 563 , September 2006 (ACM Portal) |
| MERL Report: | TR2006-128 |
| MERL Contact: | Matthew Brand |
Projection of the unit hypercube (representing all edge subsets) and the path polytope onto the (μ; σ2)-plane.
We consider the problem of finding shortest paths in a graph with independent randomly distributed edge lengths. Our goal is to maximize the probability that the path length does not exceed a given threshold value (deadline). We give a surprising exact nθ(log n) algorithm for the case of normally distributed edge lengths, which is based on quasi-convex maximization. We then prove average and smoothed polynomial bounds for this algorithm, which also translate to average and smoothed bounds for the parametric shortest path problem, and extend to a more general non-convex optimization setting. We also consider a number other edge length distributions, giving a range of exact and approximation schemes.
 | Read the full technical report (PDF: 188.1 kB) |