Title: Capacitated Covering Problems in Geometric Spaces,
Abstract: In this article, we consider the following capacitated covering problem. We
are given a set $P$ of $n$ points and a set $\mathcal{B}$ of balls from some
metric space, and a positive integer $U$ that represents the capacity of each
of the balls in $\mathcal{B}$. We would like to compute a subset $\mathcal{B}'
\subseteq \mathcal{B}$ of balls and assign each point in $P$ to some ball in
$\mathcal{B}$ that contains it, such that the number of points assigned to any
ball is at most $U$. The objective function that we would like to minimize is
the cardinality of $\mathcal{B}$.
We consider this problem in arbitrary metric spaces as well as Euclidean
spaces of constant dimension. In the metric setting, even the uncapacitated
version of the problem is hard to approximate to within a logarithmic factor.
In the Euclidean setting, the best known approximation guarantee in dimensions
$3$ and higher is logarithmic in the number of points. Thus we focus on
obtaining "bi-criteria" approximations. In particular, we are allowed to expand
the balls in our solution by some factor, but optimal solutions do not have
that flexibility. Our main result is that allowing constant factor expansion of
the input balls suffices to obtain constant approximations for these problems.
In fact, in the Euclidean setting, only $(1+\epsilon)$ factor expansion is
sufficient for any $\epsilon > 0$, with the approximation factor being a
polynomial in $1/\epsilon$. We obtain these results using a unified scheme for
rounding the natural LP relaxation; this scheme may be useful for other
capacitated covering problems. We also complement these bi-criteria
approximations by obtaining hardness of approximation results that shed light
on our understanding of these problems.