A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization

  • Yin-Tat Lee | MIT

In this talk, I will present a new algorithm for finding a point in a convex set given a separation oracle. In particular, given a separation oracle for a convex set K in Rn that is contained in a box of radius R, I will show how to either compute a point in K or prove that K does not contain a ball of radius eps using an expected O(n log(nR/eps)) evaluations of the oracle and additional time O~(n3). This improves upon the O~(n3.373) additional time of the previous fastest algorithm achieved over 25 years ago by Vaidya.

As an example, I will show how to use it to obtain a faster algorithm for the following problems: 1. Submodular Function Minimization 2. Submodular Flow 3. Matroid Intersection 4. Semidefinite Programming

Speaker Details

Yin Tat Lee is a PhD student at MIT, studying theoretical computer science under Professor Jonathan Kelner. His areas of research span convex optimization, linear programming, spectral graph theory and algorithmic graph theory. He is particularly interested in combining convex optimization and combinations techniques to design fast algorithms for fundamental optimization problems, such as linear programs, maxflow, submodular minimization, etc.

Series: Microsoft Research Talks