On Metric Multi-Covering Problems

Original · EN

In the metric multi-cover problem (MMC), we are given two point sets Y (servers) and X (clients) in an arbitrary metric space (X ∪ Y, d), a positive integer k that represents the coverage demand of each client, and a constant α≥ 1. Each server can have a single ball of arbitrary radius centered on it. Each client x ∈ X needs to be covered by at least k such balls centered on servers. The objective function that we wish to minimize is the sum of the α-th powers of the radii of the balls. In this article, we consider the MMC problem as well as some non-trivial generalizations, such as (a) the non-uniform MMC, where we allow client-specific demands, and (b) the t-MMC, where we require the number of open servers to be at most some given integer t. For each of these problems, we present an efficient algorithm that reduces the problem to several instances of the corresponding 1-covering problem, where the coverage demand of each client is 1. Our reductions preserve optimality up to a multiplicative constant factor. Applying known constant factor approximation algorithms for 1-covering, we obtain the first constant approximations for the MMC and these generalizations.