Optimization Online


A semidefinite programming hierarchy for packing problems in discrete geometry

David de Laat(mail***at***daviddelaat.nl)
Frank Vallentin(frank.vallentin***at***uni-koeln.de)

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.

Keywords: Lasserre hierarchy, weighted independence number (stability number), infinite graphs, geometric packing problems

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Infinite Dimensional Optimization (Other )


Download: [PDF]

Entry Submitted: 11/18/2013
Entry Accepted: 11/18/2013
Entry Last Modified: 11/18/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society