Lift and project relaxations for the matching and related polytopes
From MaRDI portal
Publication:1421469
DOI10.1016/S0166-218X(03)00337-8zbMath1032.05106MaRDI QIDQ1421469
Graciela L. Nasini, Silvia M. Bianchi, Néstor E. Aguilera
Publication date: 26 January 2004
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (8)
Integrality gaps for colorful matchings ⋮ A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation ⋮ Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra ⋮ Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes ⋮ On the commutativity of antiblocker diagrams under lift-and-project operators ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ On the polyhedral lift-and-project methods and the fractional stable set polytope ⋮ Unnamed Item
Cites Work
- Unnamed Item
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- On a Representation of the Matching Polytope Via Semidefinite Liftings
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Maximum matching and a polyhedron with 0,1-vertices
- When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
This page was built for publication: Lift and project relaxations for the matching and related polytopes
