Algorithms and Complexity Seminar
Monday, December 18, 2006, 4-5:15pm in 32-G575.
Stochastic Shortest Paths via Quasi-Convex Maximization
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.
Joint work with Matt Brand, Jon Kelner, and Michael Mitzenmacher.
Host: Ronitt Rubinfeld
(The Algorithms
and Complexity Seminar series talks are usually held Mondays from
4-5:15pm in 32-G575.)