On a Representation of the Matching Polytope Via Semidefinite Liftings
From MaRDI portal
Publication:2757579
DOI10.1287/moor.24.1.1zbMath0977.90078OpenAlexW2026189949MaRDI QIDQ2757579
Publication date: 26 November 2001
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.24.1.1
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (18)
Sum-of-squares rank upper bounds for matching problems ⋮ Small Chvátal rank ⋮ Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications ⋮ Integrality gaps for colorful matchings ⋮ Rank of Handelman hierarchy for Max-Cut ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ Lift and project relaxations for the matching and related polytopes ⋮ Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ 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 extracting maximum stable sets in perfect graphs using Lovász's theta function ⋮ Strong reductions for extended formulations ⋮ On the polyhedral lift-and-project methods and the fractional stable set polytope ⋮ Unnamed Item ⋮ Sum-of-Squares Rank Upper Bounds for Matching Problems ⋮ Sherali-Adams relaxations of graph isomorphism polytopes
This page was built for publication: On a Representation of the Matching Polytope Via Semidefinite Liftings
