DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2011.41

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

Authors: Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, and Avner Magen

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract

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.

Cite as

Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, and Avner Magen. Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 41-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{benabbas_et_al:LIPIcs.FSTTCS.2011.41,
  author =	{Benabbas, Siavosh and Chan, Siu On and Georgiou, Konstantinos and Magen, Avner},
  title =	{{Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{41--54},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.41},
  URN =		{urn:nbn:de:0030-drops-33299},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.41},
  annote =	{Keywords: Vertex Cover, Integrality Gap, Lift-and-Project systems, Linear Programming, Semidefinite Programming}
}

Search Results

Documents authored by Benabbas, Siavosh

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

Abstract

Cite as

Thanks for your feedback!

Could not send message