Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics

Details Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics

2006-01-05

arxiv.org/abs/cs/0601011v3

Computer Science

Data Structures and Algorithms

A more complete version. Changed order of results. A complete proof of (current) Theorem 5

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-110145