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
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\)
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60)
Cited In (6)
- Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
- 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
- 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
- Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
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)
