Rank bounds for a hierarchy of Lovász and Schrijver
From MaRDI portal
Publication:498445
DOI10.1007/s10878-013-9662-4zbMath1353.90088OpenAlexW2159431940MaRDI QIDQ498445
Publication date: 28 September 2015
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-013-9662-4
Related Items (2)
Sum-of-squares rank upper bounds for matching problems ⋮ Sum-of-Squares Rank Upper Bounds for Matching Problems
Cites Work
- Tight rank lower bounds for the Sherali-Adams proof system
- On the membership problem for the elementary closure of a polyhedron
- Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
- On a Representation of the Matching Polytope Via Semidefinite Liftings
- On the Matrix-Cut Rank of Polyhedra
- Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problems
- Hardness amplification in proof complexity
- Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász–Schrijver Procedures
- Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Integrality gaps for Sherali-Adams relaxations
- Sherali-adams relaxations of the matching polytope
- Computation of the Lasserre Ranks of Some Polytopes
- The Complexity of Propositional Proofs
- When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Rank bounds for a hierarchy of Lovász and Schrijver
