My UW | UW Search

Computer Science Home Page
[an error occurred while processing this directive] [an error occurred while processing this directive]

From shortest paths to quasi-concave minimization

In this talk I will walk through a journey of research, that started with a simple application in mind: that of finding the shortest path in an uncertain environment (or: how to get to the airport ontime). In particular, our goal was to maximize the probability that the path length does not exceed a given threshold value (deadline). This stochastic shortest path problem is one of few that have considered a nonlinear objective function--due to the difficulty of finding closed-form expressions for the objective, in addition to the challenge of optimizing the objective, which falls in the category of non-convex optimization. We give a surprising exact $n^{\Theta(log n)}$ algorithm for the case of independent normally distributed edge lengths, which is based on quasi-concave minimization.

Motivated by the stochastic shortest path problem, we further embark on giving new tools for quasi-concave minimization--a problem of considerable difficulty, whose solutions are typically exponential, and usually heuristics of unknown approximation guarantees are employeed.

To that effect, we provide the first smoothed analysis of quasi-concave minimization. The analysis is based on a smoothed bound for the number of extreme points of the projection of the feasible polytope onto a $k$-dimensional subspace. The bound we derive can be used to design a polynomial-time approximation algorithm for low-rank quasi-concave minimization (as is the case of the shortest path problem above). We supplement the positive smoothed bound with a hardness result: that general quasi-concave minimization is hard to approximate. The latter implies that our bound is tight, in that no polynomial smoothed bound is possible for general quasi-concave minimization.

This talk is based on two recent papers:
On the Hardness and Smoothed Complexity of Quasi-Concave Minimization, joint with J. Kelner (FOCS 07)
Stochastic Shortest Paths via Quasi-Convex Maximization, joint with M. Brand, J. Kelner and M. Mitzenmacher (ESA 06)

[an error occurred while processing this directive]