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

DOI10.4230/LIPICS.FSTTCS.2009.2319MaRDI QIDQ2920127zbMATH OpenOpenAlexFDO

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

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)

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

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)