<div dir="ltr">Thursday, 11/12 at 4:00 PM in LOM 215<div><div><font size="3">Yin-Tat Lee (MIT): &quot;</font><span style="line-height:19.5px"><font size="3">Cutting Plane Method: A faster algorithm for many combinatorial optimization problems&quot;</font></span></div><div><span style="line-height:19.5px"><font size="3"><br></font></span></div><div><div style="font-size:13px;line-height:19.5px"><div>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.</div><div><br></div><div>As a consequence, our algorithm yields improved runtimes for solving classic problems in continuous and combinatorial optimization such as </div><div>1) submodular minimization,</div><div>2) matroid intersection, </div><div>3) submodular flow</div><div><br></div></div></div></div></div>