Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
From MaRDI portal
Publication:5390606
DOI10.1137/080721479zbMath1209.68268OpenAlexW2023546589MaRDI QIDQ5390606
Toniann Pitassi, Konstantinos Georgiou, Iannis Tourlakis, Avner Magen
Publication date: 4 April 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/080721479
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (16)
Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Hypercontractivity of Spherical Averages in Hamming Space ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Convex Relaxations and Integrality Gaps ⋮ Semidefinite and linear programming integrality gaps for scheduling identical machines ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ Unnamed Item ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem
This page was built for publication: Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
