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

Cites Work

• Optimizing over the first Chvátal closure
• Chvátal closures for mixed integer programming problems
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• A recursive procedure to generate all cuts for 0-1 mixed integer programs
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Edmonds polytopes and a hierarchy of combinatorial problems
• Outline of an algorithm for integer solutions to linear programs
• Solving matching problems with linear programming
• Minkowski's Convex Body Theorem and Integer Programming
• Odd Minimum Cut-Sets and b-Matchings
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Disjunctive Programming
• A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• Elementary closures for integer programs.