A copositive formulation for the stability number of infinite graphs

Autor: Frank Vallentin, Mirjam Dür, Cristian Dobre, Leonhard Frerick
Jazyk: angličtina
Rok vydání: 2016
Předmět:
General Mathematics
0211 other engineering and technologies
Stability (learning theory)
Mathematics::Optimization and Control
02 engineering and technology
90C25
46N10
Wiskundige en Statistische Methoden - Biometris
01 natural sciences
Stability number
FOS: Mathematics
0101 mathematics
Completely positive cone of measures
Mathematical and Statistical Methods - Biometris
Kissing number problem
Mathematics - Optimization and Control
Mathematics
Discrete mathematics
021103 operations research
Numerical analysis
010102 general mathematics
16. Peace & justice
Cone (formal languages)
Graph
Dual (category theory)
Functional Analysis (math.FA)
Mathematics - Functional Analysis
Optimization and Control (math.OC)
Convex cone
Copositive cone of continuous Hilbert-Schmidt kernels
Variety (universal algebra)
Software
Extreme rays
Zdroj: Mathematical Programming 160 (2016) 1
Mathematical Programming, 160(1), 65-83
ISSN: 0025-5610
Popis: 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.
Comment: (v3) minor revision, 16 pages
Databáze: OpenAIRE
Externí odkaz: