2007
Integrality gaps of semidefinite programs for Vertex Cover and relations to ell$_1$ embeddability of negative type metrics
Publication
Publication
Presented at the
International Workshop on Approximation Algorithms for Combinatorial Optimization, Princeton, NJ
We study various SDP formulations for Vertex Cover by adding different constraints to the standard formulation. We rule out approximations better than
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, of
. We further show the surprising fact that by strengthening the SDP with the (intractable) requirement that the metric interpretation
of the solution embeds into ℓ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 ℓ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 to provide a
family of simple examples for negative type metrics that cannot be embedded into ℓ1 with distortion better than 8/7 − ε. To this end we prove a new isoperimetric inequality for the hypercube.
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, of
. We further show the surprising fact that by strengthening the SDP with the (intractable) requirement that the metric interpretation
of the solution embeds into ℓ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 ℓ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 to provide a
family of simple examples for negative type metrics that cannot be embedded into ℓ1 with distortion better than 8/7 − ε. To this end we prove a new isoperimetric inequality for the hypercube.
| Additional Metadata | |
|---|---|
| , , | |
| Springer | |
| M. Charikar , K. Jansen , O. Reingold , J. Rolim | |
| Lecture Notes in Computer Science | |
| Algorithmic Optimization Discretization | |
| International Workshop on Approximation Algorithms for Combinatorial Optimization | |
| Organisation | Networks and Optimization |
|
Hatami, H., Magen, A., & Markakis, V. (2007). Integrality gaps of semidefinite programs for Vertex Cover and relations to ell$_1$ embeddability of negative type metrics. In M. Charikar, K. Jansen, O. Reingold, & J. Rolim (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (pp. 164–179). Springer. |
|
