2026-07-20T04:49:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3329 2024-03-06T10:34:03Z ddc:004 open_access

Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy Benabbas, Siavosh Chan, Siu On Georgiou, Konstantinos Magen, Avner Vertex Cover Integrality Gap Lift-and-Project systems Linear Programming Semidefinite Programming We give the first tight integrality gap for Vertex Cover in the Sherali-Adams SDP system. More precisely, we show that for every \epsilon >0, the standard SDP for Vertex Cover that is strengthened with the level-6 Sherali-Adams system has integrality gap 2-\epsilon. To the best of our knowledge this is the first nontrivial tight integrality gap for the Sherali-Adams SDP hierarchy for a combinatorial problem with hard constraints. For our proof we introduce a new tool to establish Local-Global Discrepancy which uses simple facts from high-dimensional geometry. This allows us to give Sherali-Adams solutions with objective value n(1/2+o(1)) for graphs with small (2+o(1)) vector chromatic number. Since such graphs with no linear size independent sets exist, this immediately gives a tight integrality gap for the Sherali-Adams system for superconstant number of tightenings. In order to obtain a Sherali-Adams solution that also satisfies semidefinite conditions, we reduce semidefiniteness to a condition on the Taylor expansion of a reasonably simple function that we are able to establish up to constant-level SDP tightenings. We conjecture that this condition holds even for superconstant levels which would imply that in fact our solution is valid for superconstant level Sherali-Adams SDPs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siavosh Benabbas and Siu On Chan and Konstantinos Georgiou and Avner Magen 2011 Is Part Of LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2011.41 urn:nbn:de:0030-drops-33299 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.41 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode