English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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.

Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to $\ell_1$ Embeddability of Negative Type Metrics