TR2006-128

Stochastic Shortest Paths Via Quasi-convex Maximization

    •  Nikolova, E., Kelner, J., Brand, M., Mitzenmacher, M., "Stochastic Shortest Paths Via Quasi-convex Maximization", European Symposium on Algorithms (ESA), September 2006, pp. 552-563.
      BibTeX TR2006-128 PDF
      • @inproceedings{Nikolova2006sep,
      • author = {Nikolova, E. and Kelner, J. and Brand, M. and Mitzenmacher, M.},
      • title = {Stochastic Shortest Paths Via Quasi-convex Maximization},
      • booktitle = {European Symposium on Algorithms (ESA)},
      • year = 2006,
      • pages = {552--563},
      • month = sep,
      • isbn = {3-540-38875-3},
      • url = {https://www.merl.com/publications/TR2006-128}
      • }
  • MERL Contact:
  • Research Area:

    Optimization

TR Image
Projection of the unit hypercube (representing all edge subsets) and the path polytope onto the plane.
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 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.

 

  • Related News & Events

    •  NEWS    ESA 2006: publication by Matthew Brand and others
      Date: September 1, 2006
      Where: European Symposium on Algorithms (ESA)
      MERL Contact: Matthew Brand
      Brief
      • The paper "Stochastic Shortest Paths Via Quasi-convex Maximization" by Nikolova, E., Kelner, J., Brand, M. and Mitzenmacher, M. was presented at the European Symposium on Algorithms (ESA).
    •