Staff Publications

Staff Publications

  • external user (warningwarning)
  • Log in as
  • language uk
  • About

    'Staff publications' is the digital repository of Wageningen University & Research

    'Staff publications' contains references to publications authored by Wageningen University staff from 1976 onward.

    Publications authored by the staff of the Research Institutes are available from 1995 onwards.

    Full text documents are added when available. The database is updated daily and currently holds about 240,000 items, of which 72,000 in open access.

    We have a manual that explains all the features 

Record number 496983
Title A copositive formulation for the stability number of infinite graphs
Author(s) Dobre, Cristian; Dür, Mirjam; Frerick, Leonhard; Vallentin, Frank
Source Mathematical Programming 160 (2016)1. - ISSN 0025-5610 - p. 65 - 83.
DOI https://doi.org/10.1007/s10107-015-0974-2
Department(s) Biometris (WU MAT)
Publication type Refereed Article in a scientific journal
Publication year 2016
Keyword(s) Completely positive cone of measures - Copositive cone of continuous Hilbert-Schmidt kernels - Extreme rays - Stability number
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.

Comments
There are no comments yet. You can post the first one!
Post a comment
 
Please log in to use this service. Login as Wageningen University & Research user or guest user in upper right hand corner of this page.