Integrality gaps of semidefinite programs for Vertex Cover and relations to ${\ell }_1$ embeddability of Negative Type metrics

Hamed Hatami, Avner Magen, Vangelis Markakis

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…