Computer Science/Discrete Mathematics Seminar I

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 and 4) semidefinite programming. The talk will assume no exposure to cutting plane methods. It will be based on a joint work with Aaron Sidford and Sam Wong (FOCS’15). See http://arxiv.org/abs/1508.04874.