Easy and hard separation of sparse and dense odd-set constraints in matching

DOI10.1016/j.disopt.2024.100849MaRDI QIDQ6670496

Craig A. Tovey, Brady Hunsaker

Publication date: 23 January 2025

Published in: Discrete Optimization (Search for Journal in Brave)

zbMATH Keywords

separationfractional matchingperfect matching polytopesparse cutsodd-set constraints

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Graph theory (05Cxx) Polytopes and polyhedra (52Bxx)

Cites Work

• Unnamed Item
• Approximating polyhedra with sparse inequalities
• Polarity and the complexity of the shooting experiment
• A matching problem with side conditions
• Geometric algorithms and combinatorial optimization
• A simple minimum \(T\)-cut algorithm
• Corner polyhedra and their connection with cutting planes
• Worst-case comparison of valid inequalities for the TSP
• Odd Minimum Cut-Sets and b-Matchings
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
• Paths, Trees, and Flowers
• How Good Are Sparse Cutting-Planes?
• Maximum matching and a polyhedron with 0,1-vertices
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
• On disjunctive cuts for combinatorial optimization

This page was built for publication: Easy and hard separation of sparse and dense odd-set constraints in matching