1 Search Results for "Tourlakis, Iannis"


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

Authors: Konstantinos Georgiou, Avner Magen, and Iannis Tourlakis

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)


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

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)


Copy BibTex To Clipboard

@InProceedings{georgiou_et_al:LIPIcs.FSTTCS.2009.2319,
  author =	{Georgiou, Konstantinos and Magen, Avner and Tourlakis, Iannis},
  title =	{{On the Tightening of the Standard SDP for Vertex Cover with \$ell\underline1\$ Inequalities}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{203--214},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2319},
  URN =		{urn:nbn:de:0030-drops-23195},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2319},
  annote =	{Keywords: Semidefinite Programming, Vertex Cover, Integrality Gap, Hypermetric Inequalities}
}
  • Refine by Author
  • 1 Georgiou, Konstantinos
  • 1 Magen, Avner
  • 1 Tourlakis, Iannis

  • Refine by Classification

  • Refine by Keyword
  • 1 Hypermetric Inequalities
  • 1 Integrality Gap
  • 1 Semidefinite Programming
  • 1 Vertex Cover

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2009

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail