2026-08-17T16:36:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2319 2024-03-06T10:33:17Z ddc:004 open_access

On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities Georgiou, Konstantinos Magen, Avner Tourlakis, Iannis Semidefinite Programming Vertex Cover Integrality Gap Hypermetric Inequalities We show that the integrality gap of the standard SDP for \vc~on instances of $n$ vertices remains $2-o(1)$ even after the addition of \emph{all} hypermetric inequalities. Our lower bound requires new insights into the structure of SDP solutions behaving like $\ell_1$ metric spaces when one point is removed. We also show that the addition of all $\ell_1$ inequalities eliminates any solutions that are not convex combination of integral solutions. Consequently, we provide the strongest possible separation between hypermetrics and $\ell_1$ inequalities with respect to the tightening of the standard SDP for \vc. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Konstantinos Georgiou and Avner Magen and Iannis Tourlakis 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2319 urn:nbn:de:0030-drops-23195 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2319 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode