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

DOI10.1007/978-3-540-74208-1_12zbMath1171.90496OpenAlexW2570642804MaRDI QIDQ3603463

Hamed Hatami, Evangelos Markakis, Avner Magen

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)

Related Items (1)

Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack

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