COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > A semidefinite programming hierarchy for geometric packing problems

## A semidefinite programming hierarchy for geometric packing problemsAdd to your list(s) Download to your calendar using vCal - de Laat, D (Technische Universiteit Delft)
- Thursday 18 July 2013, 10:00-10:30
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Polynomial Optimisation Geometric packing problems can be modeled as maximum independent set problems in infinite graphs. Computing the independence number is NP-hard. To get a chain of improving upper bounds for finite graphs one can formulate the problem as a polynomial optimization problem and then use the Lasserre hierarchy. We generalize this hierarchy to infinite graphs using conic optimization over cones of positive kernels and measures of positive type. For finite graphs it is known that the hierarchy attains the independence number after finitely many steps. We show that this is also true for the generalized hierarchy if the infinite graph corresponds to a packing problem. Based on joint work with Frank Vallentin. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsFaith and Peace Training Opportunities Cambridge DOCking Station## Other talksBiomolecular Thermodynamics and Calorimetry (ITC) Seminar – The Cambridge Sustainable Food Hub Stopping the Biological Clock – The Lazarus factor and Pulling Life back from the Edge. Skyrmions, Quantum Graphs and Carbon-12 The race to solve the solar metallicity problem with neutrinos and discover dark matter The Warsaw Uprising in Polish Popular Culture after 1989 |