On the tightening of the standard SDP for vertex cover with _1 inequalities

DOI10.4230/LIPICS.FSTTCS.2009.2319zbMATH Open1248.68216OpenAlexW1591207959MaRDI QIDQ2920127FDOQ2920127

Authors: Konstantinos Georgiou, Avner Magen, Iannis Tourlakis 

Publication date: 24 October 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_121b.html

Recommendations

• Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities
• Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to ℓ1 Embeddability of Negative Type Metrics
• Integrality gaps of semidefinite programs for vertex cover and relations to \(\ell_1\) embeddability of negative type metrics
• Tight gaps for vertex cover in the Sherali-Adams SDP hierarchy
• Integrality gaps of \(2-o(1)\) for vertex cover SDPs in the Lovász-Schrijver hierarchy

zbMATH Keywords

semidefinite programmingintegrality gapvertex coverhypermetric inequalities

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (4)

• Tight gaps for vertex cover in the Sherali-Adams SDP hierarchy
• Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to ℓ1 Embeddability of Negative Type Metrics
• 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

This page was built for publication: On the tightening of the standard SDP for vertex cover with \(\ell_1\) inequalities

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