TIME: 3:00-4:00 pm,  Nov 7, 2007

PLACE: CSE 503  

SPEAKER: Eddie Nikolova
         MIT

TITLE:  From Shortest Paths to Quasi-Concave Minimization


ABSTRACT:
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)