Combinatorics and Probability Seminar - Yin-Tat Lee, MIT

Event time: 
Thursday, November 12, 2015 - 4:00pm
Location: 
LOM 215 See map
12 Hillhouse Avenue
New Haven, CT 06511
Event description: 

Combinatorics and Probability Seminar
Yin-Tat Lee, MIT
Title: Cutting Plane Method: A faster algorithm for many combinatorial optimization problems

Many polynomial-time solvable combinatorial optimization problems can be reduced to the feasibility problem and the intersection problem. In this talk, I will present the first nearly cubic time algorithm for both problems using a new cutting plane method. This is the first improvement over the long-standing O(n^3.38) running time bound due to Vaidya in 1989.

As a consequence, our algorithm yields improved runtimes for solving classic problems in continuous and combinatorial optimization such as 

1) submodular minimization,

2) matroid intersection, 

3) submodular flow