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

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

A semidefinite programming hierarchy for geometric packing problems

Download to your calendar using vCal

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:

Note that ex-directory lists are not shown.

Other lists

Hicks & Mead Rooms, University Centre, Granta Place University of Pennsylvania Seminar BAS Seminar Room 1; https://ukri.zoom.us/j/92279923623

Other talks

title abstract tbc A Data-Centric Approach to AI Adaptation and Alignment Polar Oceans Seminar Talk Reversals of the Geodynamo Cambridge AI in Medicine Seminar - July 2026 CSAR lecture: Beyond Net Zero: Can We Repair The Climate?
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity