[Colloq] Colloquium 12/4 Wed 10:30 AM 366WVH

[Francoise Niang]

Subject: Colloquium 12/4 Wed 10:30 AM 366WVH
From: Ravi Sundaram 

Time: 12/4 Wed, 10:30AM
Location: 366WVH

Speaker Karthikeyan Chandrasekaran

Title: A Polynomial-Time Cutting Plane Algorithm for Matching

Abstract: The cutting plane approach to optimal matchings has been discussed by several authors over the past decades [Padberg-Rao, Grotschel-Holland, Lovasz-Plummer, Trick, Fischetti-Lodi], and its convergence has been an open question. We give a cutting plane algorithm for the minimum-cost perfect matching problem using Edmonds' blossom inequalities as cuts and prove polynomial convergence of this algorithm.

Our main insight is an LP-based method to retain/drop candidate cutting planes. Our cut-addition is based on maintaining laminarity. This leads to a sequence of intermediate linear programs with a linear number of constraints whose optima are half-integral and supported by a disjoint union of odd cycles and edges. This structural property of the optima is instrumental in finding violated blossom inequalities (cuts) in linear time. The number of cycles in the support of the half-integral optima acts as a potential function to show efficient convergence to an integral solution.

Joint work with Laszlo Vegh and Santosh Vempala. 

Bio: Karthik is a Simons Postdoctoral Fellow in the Theory of Computation research group at Harvard University. He completed his Ph.D. in Algorithms, Combinatorics and Optimization (ACO) from Georgia Tech (2007-2012). His advisor was Prof. Santosh Vempala. Previously, he received his Bachelor's in Computer Science from IIT Madras (2003-2007).