CSAIL Event Calendar: Previous Series

CANCELLED: Stochastic Shortest Paths via Quasi-Convex Maximization

Speaker: Evdokia Nikolova , MIT CSAIL
Date: October 2 2006
Time: 4:00PM to 5:15PM
Location: 32-G575
Host: Madhu Sudan, MIT CSAIL

NOTE THIS TALK IS CANCELLED. It will be rescheduled.

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 Mitz
enmacher.

See other events that are part of Algorithms and Complexity Series 2006/2007

See other events happening in October 2006