A semidefinite programming hierarchy for packing problems in discrete geometry

• 成果类型: Article
• 署名作者: de laat, David; Vallentin, Frank
• 署名单位: Delft University of Technology; University of Cologne
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0843-4
• 发表日期: 2015
• 页码: 529-553
• 关键词: upper-bounds; terwilliger algebra; determinants; CODES; graph

摘要

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.