Event time:
Thursday, November 12, 2015 - 11:00am to 12:00pm
Location:
215 LOM
Speaker:
Yin-Tat Lee
Speaker affiliation:
MIT
Event description:
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