On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities

DOI10.4230/LIPIcs.FSTTCS.2009.2319zbMath1248.68216OpenAlexW1591207959MaRDI QIDQ2920127

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 programmingvertex coverintegrality gaphypermetric inequalities

Mathematics Subject Classification ID

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

This page was built for publication: On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities