A Semidefinite Programming Hierarchy for Covering Problems in Discrete Geometry

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.

Connection to LSC

Affiliated research

Co-authored by LSC co-director Cordian Riener.

More publications

Research from the LSC community.

All publications