A copositive formulation for the stability number of infinite graphs

Cristian Dobre, Mirjam Dür, Leonhard Frerick, Frank Vallentin*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

In the last decade, copositive formulations have been proposed for a variety of combinatorial optimization problems, for example the stability number (independence number). In this paper, we generalize this approach to infinite graphs and show that the stability number of an infinite graph is the optimal solution of some infinite-dimensional copositive program. For this we develop a duality theory between the primal convex cone of copositive kernels and the dual convex cone of completely positive measures. We determine the extreme rays of the latter cone, and we illustrate this theory with the help of the kissing number problem.

Original languageEnglish
Pages (from-to)65-83
JournalMathematical Programming
Volume160
Issue number1
DOIs
Publication statusPublished - 2016

Keywords

  • Completely positive cone of measures
  • Copositive cone of continuous Hilbert-Schmidt kernels
  • Extreme rays
  • Stability number

Fingerprint Dive into the research topics of 'A copositive formulation for the stability number of infinite graphs'. Together they form a unique fingerprint.

  • Cite this