Universität zu Köln

de laat, David and Vallentin, Frank ORCID: 0000-0002-3205-4607 (2015). A semidefinite programming hierarchy for packing problems in discrete geometry. Math. Program., 151 (2). S. 529 - 554. HEIDELBERG: SPRINGER HEIDELBERG. ISSN 1436-4646

Full text not available from this repository.

Abstract

Packing problems in discrete geometry can be modeled as finding independent sets in infinite graphs where one is interested in independent sets which are as large as possible. For finite graphs one popular way to compute upper bounds for the maximal size of an independent set is to use Lasserre's semidefinite programming hierarchy. We generalize this approach to infinite graphs. For this we introduce topological packing graphs as an abstraction for infinite graphs coming from packing problems in discrete geometry. We show that our hierarchy converges to the independence number.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code de laat, David UNSPECIFIED UNSPECIFIED UNSPECIFIED Vallentin, Frank UNSPECIFIED orcid.org/0000-0002-3205-4607 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-400779
DOI:	10.1007/s10107-014-0843-4
Journal or Publication Title:	Math. Program.
Volume:	151
Number:	2
Page Range:	S. 529 - 554
Date:	2015
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 UPPER-BOUNDS; TERWILLIGER ALGEBRA; DETERMINANTS; CODES; GRAPH 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/40077