Approximating the cone of copositive kernels to estimate the stability number of infinite graphs

Research output: Contribution to journalArticleScientificpeer-review

Abstract

It has been shown that the stable set problem in an infinite compact graph, and particularly the kissing number problem, reduces to an optimization problem over the cone of copositive kernels. We propose two converging hierarchies approximating this cone. Both are extensions of existing inner hierarchies for the finite dimensional copositive cone. We implement the first two levels of the new hierarchies for the kissing number problem.
Original languageEnglish
Pages (from-to)303-308
JournalElectronic Notes in Discrete Mathematics
Volume62
DOIs
Publication statusPublished - Nov 2017

Fingerprint

Stability number
Infinite Graphs
Cone
kernel
Estimate
Stable Set
Optimization Problem
Graph in graph theory
Hierarchy

Keywords

  • copositive programming
  • semi-definite approximations
  • lifting
  • kissing number

Cite this

@article{44bd101c840a4621baf53c7d8a6a5f9b,
title = "Approximating the cone of copositive kernels to estimate the stability number of infinite graphs",
abstract = "It has been shown that the stable set problem in an infinite compact graph, and particularly the kissing number problem, reduces to an optimization problem over the cone of copositive kernels. We propose two converging hierarchies approximating this cone. Both are extensions of existing inner hierarchies for the finite dimensional copositive cone. We implement the first two levels of the new hierarchies for the kissing number problem.",
keywords = "copositive programming, semi-definite approximations, lifting, kissing number",
author = "Olga Kuryatnikova and {Vera Lizcano}, Juan",
note = "Part of special issue: LAGOS'17 – IX Latin and American Algorithms, Graphs and Optimization Edited by Fr{\'e}d{\'e}rique Bassino, Flavia Bonomo, Lionel Pournin, Mario Valencia-Pabon, Juan Carlos Vera Lizcano",
year = "2017",
month = "11",
doi = "10.1016/j.endm.2017.10.052",
language = "English",
volume = "62",
pages = "303--308",
journal = "Electronic Notes in Discrete Mathematics",
issn = "1571-0653",
publisher = "Elsevier",

}

Approximating the cone of copositive kernels to estimate the stability number of infinite graphs. / Kuryatnikova, Olga; Vera Lizcano, Juan.

In: Electronic Notes in Discrete Mathematics, Vol. 62, 11.2017, p. 303-308.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Approximating the cone of copositive kernels to estimate the stability number of infinite graphs

AU - Kuryatnikova, Olga

AU - Vera Lizcano, Juan

N1 - Part of special issue: LAGOS'17 – IX Latin and American Algorithms, Graphs and Optimization Edited by Frédérique Bassino, Flavia Bonomo, Lionel Pournin, Mario Valencia-Pabon, Juan Carlos Vera Lizcano

PY - 2017/11

Y1 - 2017/11

N2 - It has been shown that the stable set problem in an infinite compact graph, and particularly the kissing number problem, reduces to an optimization problem over the cone of copositive kernels. We propose two converging hierarchies approximating this cone. Both are extensions of existing inner hierarchies for the finite dimensional copositive cone. We implement the first two levels of the new hierarchies for the kissing number problem.

AB - It has been shown that the stable set problem in an infinite compact graph, and particularly the kissing number problem, reduces to an optimization problem over the cone of copositive kernels. We propose two converging hierarchies approximating this cone. Both are extensions of existing inner hierarchies for the finite dimensional copositive cone. We implement the first two levels of the new hierarchies for the kissing number problem.

KW - copositive programming

KW - semi-definite approximations

KW - lifting

KW - kissing number

U2 - 10.1016/j.endm.2017.10.052

DO - 10.1016/j.endm.2017.10.052

M3 - Article

VL - 62

SP - 303

EP - 308

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -