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