Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics
<|reference_start|>Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics: 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.<|reference_end|>
@article{hatami2006integrality,
    title={Integrality gaps of semidefinite programs for Vertex Cover and relations
  to $\ell_1$ embeddability of Negative Type metrics},
    author={Hamed Hatami and Avner Magen and Vangelis Markakis},
    journal={arXiv preprint arXiv:cs/0601011},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0601011},
    primaryClass={cs.DS cs.DM math.MG}
}