Fall 2009 Seminar Series

DATE:October 1st
LOCATION: E51-325
TIME: 4:15pm
Reception immediately following in the ORC ConferenceRoom, E40-106

SPEAKER:
Santosh Vempala

TITLE
Efficient Algorithms for Some Nonconvex Families

ABSTRACT
Star-shaped bodies are an important nonconvex generalization of convex bodies (e.g., linear programming with some violations). We present an efficient algorithm for sampling a given star-shaped body. The complexity of the algorithm grows polynomially in the dimension and inverse polynomially in the fraction of the volume taken up by the kernel of the star-shaped body. Our analysis is based on a new isoperimetric inequality, which is based on a new tool for proving such inequalities when the domain is not convex. As a consequence, we obtain a polynomial algorithm for computing the volume of such a body as well. In contrast, linear optimization over star-shaped sets is NP-hard. We will also discuss other nonconvex sets to which our tool can be applied.

 

This is joint work with Karthekeyan Chandrasekaran and Daniel Dadush.