When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
From MaRDI portal
Publication:5704055
DOI10.1287/moor.26.4.796.10012zbMath1082.90548arXivmath/0006036OpenAlexW2167508847MaRDI QIDQ5704055
Michel X. Goemans, Tunçel, Levent
Publication date: 11 November 2005
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0006036
Related Items
Sum-of-squares rank upper bounds for matching problems, Integrality gaps for strengthened linear relaxations of capacitated facility location, Tree-width and the Sherali-Adams operator, Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators, Sum of Squares Bounds for the Empty Integral Hull Problem, Sum-of-squares hierarchy lower bounds for symmetric formulations, On polytopes with linear rank with respect to generalizations of the split closure, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Tightening simple mixed-integer sets with guaranteed bounds, 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, Approximate formulations for 0-1 knapsack sets, 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, Elementary closures for integer programs., Unnamed Item, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, Valid inequalities for mixed integer linear programs, On the polyhedral lift-and-project methods and the fractional stable set polytope, Sum-of-Squares Rank Upper Bounds for Matching Problems, Approximate fixed-rank closures of covering problems, Superlinear Integrality Gaps for the Minimum Majority Problem
