2012/07/24 by Karthekeyan Chandrasekaran, Chandrasekaran, Karthekeyan, László A. Végh +3
Computer Science · Economics, Econometrics and Finance · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1207.5813
openalex publication_date 2012/07/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The cutting plane approach to optimal matchings has been discussed by several authors over the past decades (e.g., Padberg and Rao '82, Grotschel and Holland '85, Lovasz and Plummer '86, Trick '87, Fischetti and Lodi '07) and its convergence has been an open question. We give a cutting plane algorithm that converges in polynomial-time using only Edmonds' blossom inequalities; it maintains half-integral intermediate LP solutions supported by a disjoint union of odd cycles and edges. Our main insight is a method to retain only a subset of the previously added cutting planes based on their dual values. This allows us to quickly find violated blossom inequalities and argue convergence by tracking the number of odd cycles in the support of intermediate solutions.