Аннотация:We study various semidefinite programming (SDP) formulations for Vertex Cover by adding different constraints to the standard formulation. We show that Vertex Cover cannot be approximated better than $2-O(\sqrt{\log\log n/\log n})$ even when we add the so-called pentagonal inequality constraints to the standard SDP formulation, and thus almost meet the best upper bound known due to Karakostas [Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, 2005], of $2-\Omega(\sqrt{1/\log n})$. We further show the surprising fact that by strengthening the SDP with the (intractable) requirement that the metric interpretation of the solution embeds into $\ell_1$ with no distortion, 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 is $2-o(1)$. Finally, inspired by the above findings, we use ideas from the integrality gap construction of Charikar [SODA '02: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2002, pp. 616–620] to provide a family of simple examples for negative type metrics that cannot be embedded into $\ell_1$ with distortion better than $8/7-\epsilon$. To this end we prove a new isoperimetric inequality for the hypercube.
