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

Olga Kuryatnikova; J.C. Vera

doi:10.1016/j.endm.2017.10.052

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

Olga Kuryatnikova, J.C. Vera

Research output: Contribution to journal › Article › Scientific › peer-review

1 Citation (Scopus)

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 language	English
Pages (from-to)	303-308
Journal	Electronic Notes in Discrete Mathematics
Volume	62
DOIs	https://doi.org/10.1016/j.endm.2017.10.052
Publication status	Published - Nov 2017

Keywords

copositive programming
semi-definite approximations
lifting
kissing number

Access to Document

10.1016/j.endm.2017.10.052

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 J.C. Vera",

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 = nov,

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",

}

TY - JOUR

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

AU - Kuryatnikova, Olga

AU - Vera, J.C.

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

SN - 1571-0653

VL - 62

SP - 303

EP - 308

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this