Sherali-adams relaxations of the matching polytope

DOI10.1145/1536414.1536456zbMath1304.90144OpenAlexW2148872782MaRDI QIDQ5172723

Claire Mathieu, Alistair Sinclair

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536456

zbMATH Keywords

maximum matching0-1 programminglinear programming relaxationintegrality gapmatching polytopelift-and-project

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Sum-of-squares rank upper bounds for matching problems ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Integrality gaps for colorful matchings ⋮ Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ 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 linear and semidefinite programming relaxations for hypergraph matching ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope ⋮ Sum-of-Squares Rank Upper Bounds for Matching Problems ⋮ Sherali-Adams relaxations of graph isomorphism polytopes ⋮ Symmetry-exploiting cuts for a class of mixed-\(0/1\) second-order cone programs ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem

This page was built for publication: Sherali-adams relaxations of the matching polytope