LIPIcs.FSTTCS.2009.2319.pdf
- Filesize: 127 kB
- 12 pages
Document
On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities
Authors
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2009-12-14
Cite AsGet BibTex
Konstantinos Georgiou, Avner Magen, and Iannis Tourlakis. On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 203-214, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2319
https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2319
Abstract
We show that the integrality gap of the standard SDP for \vc~on instances of $n$ vertices remains $2-o(1)$ even after
the addition of \emph{all} hypermetric inequalities. Our lower bound requires new insights into the structure of SDP
solutions behaving like $\ell_1$ metric spaces when one point is removed. We also show that the addition of all
$\ell_1$ inequalities eliminates any solutions that are not convex combination of integral solutions. Consequently, we
provide the strongest possible separation between hypermetrics and $\ell_1$ inequalities with respect to the
tightening of the standard SDP for \vc.
Keywords
- Semidefinite Programming
- Vertex Cover
- Integrality Gap
- Hypermetric Inequalities
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads