Preprint
On Metric Multi-Covering Problems
ArXiv.org
02/12/2016
DOI: 10.48550/arxiv.1602.04152
Abstract
In the metric multi-cover problem (MMC), we are given two point sets $Y$
(servers) and $X$ (clients) in an arbitrary metric space $(X \cup Y, d)$, a
positive integer $k$ that represents the coverage demand of each client, and a
constant $\alpha \geq 1$. Each server can have a single ball of arbitrary
radius centered on it. Each client $x \in 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 $\alpha$-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.
Details
- Title: Subtitle
- On Metric Multi-Covering Problems
- Creators
- Santanu BhowmickTanmay InamdarKasturi Varadarajan
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.1602.04152
- ISSN
- 2331-8422
- Language
- English
- Date posted
- 02/12/2016
- Academic Unit
- Computer Science
- Record Identifier
- 9984411257202771
Metrics
1 Record Views