The cutting plane method is polynomial for perfect matchings

Karthekeyan Chandrasekaran, László A. Végh, Santosh Vempala

Research output: Contribution to journalConference articlepeer-review

Abstract

The cutting plane approach to optimal matchings has been discussed by several authors over the past decades, and its rate of convergence has been an open question. We prove that the cutting plane approach using Edmonds' blossom inequalities converges in polynomial time for the minimum-cost perfect matching problem. Our main insight is an LP-based method to select cutting planes. This cut selection procedure 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. Moreover, 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.

Original languageEnglish (US)
Article number6375336
Pages (from-to)571-580
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - 2012
Externally publishedYes
Event53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States
Duration: Oct 20 2012Oct 23 2012

Keywords

  • algorithms
  • cutting plane methods
  • matching

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'The cutting plane method is polynomial for perfect matchings'. Together they form a unique fingerprint.

Cite this