Stochastic shortest paths via quasi-convex maximization. (English) Zbl 1131.05317
Azar, Yossi (ed.) et al., Algorithms – ESA 2006. 14th annual European symposium, Zurich, Switzerland, September 11–13, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-38875-3/pbk). Lecture Notes in Computer Science 4168, 552-563 (2006).
Summary: 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^{\Theta (\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.
For the entire collection see [Zbl 1130.68002].
For the entire collection see [Zbl 1130.68002].
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 90C35 | Programming involving graphs or networks |
| 90C59 | Approximation methods and heuristics in mathematical programming |
