The Cutting Plane Method is Polynomial for Perfect Matchings
DOI10.1287/moor.2015.0714zbMath1334.90077arXiv1207.5813OpenAlexW2568763528MaRDI QIDQ2800362
Karthekeyan Chandrasekaran, László A. Végh, Santosh Vempala
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
graph theorymatchingscutting planesinteger programslinear programsblossom inequalitieshalf-integrality
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10)
Related Items (5)
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.
This page was built for publication: The Cutting Plane Method is Polynomial for Perfect Matchings
