[Combprob] Thursday (11/12): Yin-Tat Lee (MIT): "Cutting Plane Method: A faster algorithm for many combinatorial optimization problems"

[Daniel Spielman]

Thursday, 11/12 at 4:00 PM in LOM 215
Yin-Tat Lee (MIT): "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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/combprob/attachments/20151110/55c5f216/attachment.html