Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to ℓ1 Embeddability of Negative Type Metrics

DOI10.1007/978-3-540-74208-1_12zbMATH Open1171.90496OpenAlexW2570642804MaRDI QIDQ3603463FDOQ3603463

Authors Hamed Hatami, Avner Magen, Evangelos Markakis 

Publication date 17 February 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74208-1_12

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Integrality gaps of semidefinite programs for vertex cover and relations to \(\ell_1\) embeddability of negative type metrics
• Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities
• On the tightening of the standard SDP for vertex cover with \(\ell_1\) inequalities
• Integrality gaps of \(2-o(1)\) for vertex cover SDPs in the Lovász-Schrijver hierarchy
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)

Cited in

(6)

• Integrality gaps of semidefinite programs for vertex cover and relations to \(\ell_1\) embeddability of negative type metrics
• On the tightening of the standard SDP for vertex cover with \(\ell_1\) inequalities
• Integrality gaps of linear and semi-definite programming relaxations for knapsack
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
• Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3603463)