Stochastic Shortest Paths Via Quasi-convex Maximization

Evdokia Nikolova, Jonathan A. Kelner, Matthew Brand, Michael Mitzenmacher

Abstract

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.
BibTeX
@inproceedings{nikolova2006stochastic,
  author = {Evdokia Nikolova and Jonathan A. Kelner and Matthew Brand and Michael Mitzenmacher},
  title = {{Stochastic Shortest Paths Via Quasi-convex Maximization}},
  booktitle = {ESA},
  year = {2006},
  doi = {10.1007/11841036\_50},
}

Loading related content...

Figure