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

zbMATH Keywords

graph theorymatchingscutting planesinteger programslinear programsblossom inequalitieshalf-integrality

Mathematics Subject Classification ID

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)

Theoretical challenges towards cutting-plane selection ⋮ Revisiting a cutting-plane method for perfect matchings ⋮ When the Gomory-chvátal closure coincides with the integer hull ⋮ A detailed introduction to a minimum-cost perfect matching algorithm based on linear programming ⋮ Computing in combinatorial optimization

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