A semidefinite programming hierarchy for covering problems in Discrete Geometry

Riener C, Rolfes J, Vallentin F (2024)

Publication Status: Submitted

Publication Type: Unpublished / Preprint

Future Publication Type: Journal article

Publication year: 2024

DOI: 10.48550/arXiv.2312.11267

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.

Authors with CRIS profile

Jan Rolfes Economics - Discrete Optimization - Mathematics (EDOM)

Involved external institutions

Universitetet i Tromsø / The Arctic University of Norway (UiT) NO Norway (NO) Universität zu Köln DE Germany (DE)

How to cite

APA:

Riener, C., Rolfes, J., & Vallentin, F. (2024). A semidefinite programming hierarchy for covering problems in Discrete Geometry. (Unpublished, Submitted).

MLA:

Riener, Cordian, Jan Rolfes, and Frank Vallentin. A semidefinite programming hierarchy for covering problems in Discrete Geometry. Unpublished, Submitted. 2024.

BibTeX: Download