Covering compact metric spaces greedily

Rolfes J, Vallentin F (2018)

Publication Language: English

Publication Type: Journal article

Publication year: 2018

Journal

Acta Mathematica Hungarica Akadémiai Kiadó / Springer Verlag (Germany)

Book Volume: 155

Pages Range: 130--140

Journal Issue: 1

DOI: 10.1007/s10474-018-0829-4

Abstract

A general greedy approach to construct coverings of compact metric spaces by metric balls is given and analyzed. The analysis is a continuous version of Chvátal's analysis of the greedy algorithm for the weighted set cover problem. The approach is demonstrated in an exemplary manner to construct efficient coverings of the n-dimensional sphere and n-dimensional Euclidean space to give short and transparent proofs of several best known bounds obtained from constructions in the literature on sphere coverings.

Authors with CRIS profile

Jan Rolfes Economics - Discrete Optimization - Mathematics (EDOM)

Involved external institutions

Universität zu Köln DE Germany (DE)

How to cite

APA:

Rolfes, J., & Vallentin, F. (2018). Covering compact metric spaces greedily. Acta Mathematica Hungarica, 155(1), 130--140. https://dx.doi.org/10.1007/s10474-018-0829-4

MLA:

Rolfes, Jan, and Frank Vallentin. "Covering compact metric spaces greedily." Acta Mathematica Hungarica 155.1 (2018): 130--140.

BibTeX: Download