We study various SDP formulations for {sc Vertex Cover} by adding different constraints to the standard formulation. We show that {sc Vertex Cover} cannot be approximated better than $2-o(1)$ even when we add the so called pentagonal inequality constraints to the standard SDP formulation, en route answering an open question of Karakostas~cite{Karakostas}. We further show the surprising fact that by strengthening the SDP with the (intractable) requirement that the metric interpretation of the solution is an $ell_1$ metric, we get an exact relaxation (integrality gap is 1), and on the other hand if the solution is arbitrarily close to being $ell_1$ embeddable, the integrality gap may be as big as $2-o(1)$. Finally, inspired by the above findings, we use ideas from the integrality gap construction of Charikar cite{Char02} to provide a family of simple examples for negative type metrics that cannot be embedded into $ell_1$ with distortion better than $8/7-eps$. To this end we prove a new isoperimetric inequality for the hypercube.
تحميل البحث