The Cutting Plane Method is Polynomial for Perfect Matchings

DOI10.1287/moor.2015.0714zbMath1334.90077arXiv1207.5813MaRDI QIDQ2800362

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

Publication date: 15 April 2016

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.5813

zbMATH Keywords

graph theory; matchings; cutting planes; integer programs; linear programs; blossom inequalities; half-integrality

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

90C10: Integer programming

68R10: Graph theory (including graph drawing) in computer science