The Cutting Plane Method is Polynomial for Perfect Matchings

• 成果类型: Article
• 署名作者: Chandrasekaran, Karthekeyan; Vegh, Laszlo A.; Vempala, Santosh S.
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University of London; London School Economics & Political Science; University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2015.0714
• 发表日期: 2016
• 页码: 23-48
• 关键词: integer; closures

摘要

The cutting plane approach to finding minimum-cost perfect matchings has been discussed by several authors over past decades. Its convergence has been an open question. We develop a cutting plane algorithm that converges in polynomial-time using only Edmonds' blossom inequalities, and which 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.