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

Georgiou, Konstantinos; Magen, Avner; Tourlakis, Iannis

doi:10.4230/LIPIcs.FSTTCS.2009.2319

Document

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

Authors Konstantinos Georgiou, Avner Magen, Iannis Tourlakis

Part of: Volume: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: 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

PDF

File

PDF

LIPIcs.FSTTCS.2009.2319.pdf

Filesize: 127 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2009.2319
URN: urn:nbn:de:0030-drops-23195

Subject Classification

Keywords

Semidefinite Programming
Vertex Cover
Integrality Gap
Hypermetric Inequalities

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get 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

Author Details

Konstantinos Georgiou

Avner Magen

Iannis Tourlakis

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail