A semidefinite programming hierarchy for covering problems in discrete geometry
Cordian Riener, Jan Rolfes, Frank Vallentin · Numerical Algebra Control and Optimization · 2025
In this paper, we present a new semidefinite programming hierarchy for covering problems in compact metric spaces.In recent years, these kind of hierarchies were developed primarily for geometric packing and for energy minimization problems, and 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.