Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy

DOI10.4230/LIPIcs.FSTTCS.2011.41zbMath1246.68260OpenAlexW2286706273MaRDI QIDQ2911610

Siu-On Chan, Siavosh Benabbas, Konstantinos Georgiou, Avner Magen

Publication date: 31 August 2012

Full work available at URL: https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.41

zbMATH Keywords

linear programmingsemidefinite programmingvertex coverintegrality gaplift-and-project systems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Linear programming (90C05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph

This page was built for publication: Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy