Universität zu Köln

Dobre, Cristian, Duer, Mirjam, Frerick, Leonhard and Vallentin, Frank ORCID: 0000-0002-3205-4607 (2016). A copositive formulation for the stability number of infinite graphs. Math. Program., 160 (1-2). S. 65 - 84. HEIDELBERG: SPRINGER HEIDELBERG. ISSN 1436-4646

Full text not available from this repository.

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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Dobre, Cristian UNSPECIFIED UNSPECIFIED UNSPECIFIED Duer, Mirjam UNSPECIFIED UNSPECIFIED UNSPECIFIED Frerick, Leonhard UNSPECIFIED UNSPECIFIED UNSPECIFIED Vallentin, Frank UNSPECIFIED orcid.org/0000-0002-3205-4607 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-257549
DOI:	10.1007/s10107-015-0974-2
Journal or Publication Title:	Math. Program.
Volume:	160
Number:	1-2
Page Range:	S. 65 - 84
Date:	2016
Publisher:	SPRINGER HEIDELBERG
Place of Publication:	HEIDELBERG
ISSN:	1436-4646
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Mathematical Institute
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language QUADRATIC OPTIMIZATION PROBLEMS Multiple languages Computer Science, Software Engineering; Operations Research & Management Science; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/25754