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.

Cornell University Library
M. Charikar , K. Jansen , O. Reingold , J. Rolim
arXiv.org e-Print archive
Algorithmic Optimization Discretization
International Workshop on Approximation Algorithms for Combinatorial Optimization
Networks and Optimization

Hatami, H., Magen, A., & Markakis, V. (2006). Integrality gaps of semidefinite programs for Vertex Cover and relations to ell$_1$ embeddability of negative type metrics. (M. Charikar, K. Jansen, O. Reingold, & J. Rolim, Eds.)arXiv.org e-Print archive. Cornell University Library .