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

Simple item page
dc.creatorHatami, Hamed
dc.creatorMagen, Avner
dc.creatorMarkakis, Vangelis
dc.date2006-01-05
dc.date2006-04-13
dc.date.accessioned2026-07-07T06:57:52Z
dc.date.available2026-07-07T06:57:52Z
dc.descriptionWe 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.
dc.descriptionA more complete version. Changed order of results. A complete proof of (current) Theorem 5
dc.identifierhttps://arxiv.org/abs/cs/0601011
dc.identifierhttp://arxiv.org/abs/cs/0601011
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/107137
dc.subjectData Structures and Algorithms
dc.subjectDiscrete Mathematics
dc.subjectMetric Geometry
dc.titleIntegrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics
dc.typetext

Files

Collections

arXiv