Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes

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

zbMATH Keywords

integer programmingsemidefinite programmingconvex relaxationsmatching polytopelift-and-project methods

Mathematics Subject Classification ID

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