A semidefinite programming hierarchy for covering problems in discrete geometry
arXiv:2312.11267 · doi:10.3934/naco.2025015
Abstract
In this paper we present a new semidefinite programming hierarchy for covering problems in compact metric spaces. Over the last years, these kind of hierarchies were developed primarily for geometric packing and for energy minimization problems; they frequently provide the best known bounds. Starting from a semidefinite programming hierarchy for the dominating set problem in graph theory, we derive the new hierarchy for covering and show some of its basic properties: The hierarchy converges in finitely many steps, but the first level collapses to the volume bound when the compact metric space is homogeneous.
(v2) 14 pages, referees comments incorporated, accepted in Numerical Algebra, Control and Optimization (NACO), special issue on "POP23 - Future Trends in Polynomial Optimization"
References in corpus (5)
- New upper bounds for kissing numbers from semidefinite programming
- A semidefinite programming hierarchy for packing problems in discrete geometry
- Lower bounds for measurable chromatic numbers
- Moment methods in energy minimization: New bounds for Riesz minimal energy problems
- Covering compact metric spaces greedily