Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
From MaRDI portal
Publication:3009747
DOI10.1007/978-3-642-20807-2_2zbMath1298.90054OpenAlexW44589754MaRDI QIDQ3009747
Tunçel, Levent, Yu Hin (Gary) Au
Publication date: 24 June 2011
Published in: Integer Programming and Combinatoral Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-20807-2_2
integer programmingsemidefinite programmingconvex relaxationsmatching polytopelift-and-project methods
Semidefinite programming (90C22) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Related Items
Sum-of-squares rank upper bounds for matching problems ⋮ On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ Integrality gaps for colorful matchings ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Strong reductions for extended formulations ⋮ Sum-of-Squares Rank Upper Bounds for Matching Problems ⋮ Sherali-Adams relaxations of graph isomorphism polytopes
Cites Work
- Unnamed Item
- Disjunctive programming: Properties of the convex hull of feasible points
- Lift and project relaxations for the matching and related polytopes
- The stable set problem and the lift-and-project ranks of graphs
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- 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
- Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure
- Theta Bodies for Polynomial Ideals
- 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
- Subset Algebra Lift Operators for 0-1 Integer Programming
- Sherali-adams relaxations of the matching polytope
- Computation of the Lasserre Ranks of Some Polytopes
- Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
- On Lovász--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP
- 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
This page was built for publication: Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
