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

DOI10.1137/070700103zbMath1187.90218arXivcs/0601011OpenAlexW1560060719MaRDI QIDQ5189507

Evangelos Markakis, Avner Magen, Hamed Hatami

Publication date: 17 March 2010

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0601011

zbMATH Keywords

semidefinite programmingvertex coverintegrality gap

Mathematics Subject Classification ID

Semidefinite programming (90C22) Embedding (54C25) Approximation algorithms (68W25)

Related Items (1)

Specified intersections

This page was built for publication: Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to $\ell_1$ Embeddability of Negative Type Metrics