|
|
|
Fall 2009 Seminar Series
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
OPERATIONS RESEARCH CENTER
FALL 2009 SEMINAR SERIES
DATE:October 1st
LOCATION: E51-325
TIME: 4:15pm
Reception immediately following in the ORC ConferenceRoom, E40-106
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.
Back to Seminar Series schedule page |
|
|
|
|