11institutetext: Department of Computer Science and Engineering, IIT Delhi

# FPT Approximation for Capacitated Sum of Radii

Ragesh Jaiswal  Amit Kumar and Jatin Yadav

###### Abstract

We consider the capacitated clustering problem in general metric spaces where
the goal is to identify $k$ clusters and minimize the sum of the radii of the
clusters (we call this the Capacitated $k$-sumRadii problem). We are
interested in fixed-parameter tractable (FPT) approximation algorithms where
the running time is of the form $f(k)\cdot{\mathsf{poly}}(n)$, where $f(k)$
can be an exponential function of $k$ and $n$ is the number of points in the
input. In the uniform capacity case, Bandyapadhyay et al. recently gave a
$4$-approximation algorithm for this problem. Our first result improves this
to an FPT $3$-approximation and extends to a constant factor approximation for
any $L_{p}$ norm of the cluster radii. In the general capacities version,
Bandyapadhyay et al. gave an FPT $15$-approximation algorithm. We extend their
framework to give an FPT $(4+\sqrt{13})$-approximation algorithm for this
problem. Our framework relies on a novel idea of identifying approximations to
optimal clusters by carefully pruning points from an initial candidate set of
points. This is in contrast to prior results that rely on guessing suitable
points and building balls of appropriate radii around them.

On the hardness front, we show that assuming the Exponential Time Hypothesis,
there is a constant $c>1$ such that any $c$-approximation algorithm for the
non-uniform capacity version of this problem requires running time
$2^{\Omega\left(\frac{k}{polylog(k)}\right)}$.

##  1 Introduction

Center-based clustering problems are important data processing tasks. Given a
metric $D$ on a set of $n$ points $\mathcal{X}$ and a parameter $k$, the goal
here is to partition the set of points into $k$ clusters, say
$C_{1},\ldots,C_{k}$, and assign the points in each cluster to a corresponding
cluster center, say $c_{1},\ldots,c_{k}$, respectively. Some of the most
widely studied objective functions are given by the $k$-center, the $k$-median
and the $k$-means problems. The $k$-center problem seeks to find a clustering
such that the maximum radius of a cluster is minimized. Here, radius of a
cluster is defined as the farthest distance between the center of the cluster
and a point in the same cluster. Another important center based objective
function is the $k$-sumRadii problem where the goal is to minimize the sum of
the radii of the $k$ clusters. Besides being an interesting problem in its own
right, the $k$-sumRadii problem is sometimes preferred over the $k$-center
problem because it avoids the so-called dissection effect: an optimal
$k$-center solution may place several pairs of close points in two different
clusters ([13, 7]). The problem is known to be $\mathsf{NP}$-hard even in
metrics defined by weighted planar graphs and in metrics of constant doubling
dimension [11]. Gibson et al. [11] gave an exact randomised algorithm with
running time $n^{O(\log{n}\cdot\log{\Delta})}$, where $\Delta$ denotes the
aspect ratio (i.e., max. to min. interpoint distance). They also gave a
randomised $(1+\varepsilon)$-approximation algorithm with running time
$n^{O(\log{n}\cdot\log{\frac{n}{\varepsilon}})}$. Interestingly, there is a
polynomial time algorithm [12] for a special case of points on a plane, where
the problem is to cover points using disks.

The $k$-sumRadii problem was first considered from the approximation
algorithms perspective by Doddi et al. [9]. They gave a bi-criteria
logarithmic approximation algorithm with $O(k)$ clusters for $k$-sumRadii.
Charikar and Panigrahy [6] improved this result to give the first constant
factor 3.504-approximation algorithm for this problem. Using coreset based
techniques of Bădoiu et al. [5], one can obtain a
$(1+\varepsilon)$-approximation $2^{O(\frac{k\log{k}}{\varepsilon^{2}})}\cdot
dn^{O(1)}$-time algorithm in the Euclidean setting. Note that all the works
mentioned above have been on the uncapacitated version of the problem where
there is no upper limit on the number of points that can be assigned to a
center.

In this paper, we consider the Capacitated $k$-sumRadii problem, where each
data point $p$ also specifies a capacity $U_{p}$ – this is an upper bound on
the size of a cluster centered at $p$. It is worth noting that we only
consider the so-called hard capacitated setting: multiple centers cannot be
opened at the same point. Capacitated versions of clustering problems have
been well-studied in the literature and arise naturally in practical settings.
Although constant factor approximation algorithm is known for the Capacitated
$k$-center problem, obtaining a similar result for the Capacitated $k$-median
remains a challenging open problem.

Motivated by the above discussion, we consider the Capacitated $k$-sumRadii
problem in the FPT setting. We seek algorithms which have constant
approximation ratio but their running time can be of the form
$f(k){\mathsf{poly}}(n)$, where $f(k)$ can be an exponential function of $k$
(and hence, such algorithms are FPT with respect to the parameter $k$).
Inamdar and Vardarajan [15] had considered this problem in the special case of
uniform capacities, i.e., each point in the input has the same capacity. They
gave a 28-approximation algorithm with running time
$2^{O(k^{2})}{\mathsf{poly}}(n)$. This was subsequently improved by
Bandyapadhyay et al. [2] who gave an FPT $(4+\varepsilon)$-approximation
algorithm for the uniform capacity setting. The running time of their
algorithm crucially uses the fact that objective function is the sum, i.e.,
the $L_{1}$-norm, of the radii of the clusters. Our first result improves this
to an FPT $(3+\varepsilon)$-approximation algorithm. Further, our result
extends to a constant factor approximation ratio for any $L_{p}$ norm, where
$p\geq 1$.

Bandyapadhyay et al. [2] also considered the general (i.e., non-uniform
capacities) Capacitated $k$-sumRadii problem and gave an FPT
$(15+\varepsilon)$-approximation algorithm for this problem. Their argument
also extends to general $L_{p}$ norm. However, it turns out that one of the
arguments in their proof is incomplete and requires a deeper argument.
Motivated by our insights, we refine and extend their proof which not only
corrects this step but also yields a better FPT
$(9+\varepsilon)$-approximation algorithm. A careful parameter balancing
improves this to about 7.6-approximation. Our result also extends to any
$L_{p}$ norm of cluster radii, where $p\geq 1$.

Our final result shows that there exists a constant $C>1$ such that, assuming
ETH, any $C$-approximation algorithm for Capacitated $k$-sumRadii (in the non-
uniform capacity setting) must have exponential running time. This also rules
out polynomial time approximation algorithms with approximation ratio better
than $C$.

###  1.1 Our Results and Techniques

In this section, we give a more formal description of our results. Our first
result is concerned with the Capacitated $k$-sumRadii problem with uniform
capacities. The first few steps in our algorithm are analogous to those of
[2]. Suppose we can guess the radii of the clusters in an optimal solution,
say $r_{1}^{\star},\ldots,r_{k}^{\star}$. Let $C_{i}^{\star}$ denote the set
of points in an optimal cluster. We call a cluster large if it has at least
$U/k^{3}$ points (where $U$ denotes the uniform capacity at each point).
Again, we can guess the radii of the optimal large clusters in FPT time.
Assume that there are $k_{L}$ large clusters with radii
$r_{1}^{\star},\ldots,r_{k_{L}}^{\star}$. It is not hard to show that we can
sample one point $p_{i}$ from each large cluster with reasonably high
probability. Thus, for each large cluster of radius say $r_{i}^{\star}$, we
can find a ball $B_{i}$ of radius $2r_{i}^{\star}$ containing it – the center
of such a ball would be the sampled point $p_{i}$ as above. Now suppose the
union of all of the balls $B_{i},i\in[k_{L}^{\star}]$, covers the entire set
of points (although this is a special scenario, it captures the non-triviality
of the algorithm). At this moment, we cannot assign all the points to the
chosen centers $p_{i}$ because of the capacity constraint. The approach of [2]
is the following: consider a graph where the vertex set corresponds to the
small optimal balls (i.e., $C_{i}^{\star},i>k_{L}^{\star}$) and the balls
$B_{i},i\in[k_{L}^{\star}]$ constructed by our algorithm. We have an edge
between two vertices here if the corresponding sets intersect. Since this is a
graph on $k$ vertices, we can guess this graph. Now for each connected
component in this graph, we can have a single ball whose radius is the sum of
the radii of the participating balls in this graph. It is not hard to show
that such large radii balls can cover all the small balls and hence can
account for the capacity deficit due to the balls $B_{i},i\in[k_{L}^{\star}]$.
Thus one incurs an additional 2-factor loss in the approximation ratio here,
resulting in a 4-approximation algorithm. Further, the fact that the algorithm
chooses a radius which is the sum of several optimal radii shows that this
approach does not extend to $L_{p}$ norm of radii.

Our approach is the following: the union of the balls $B_{i}$ selected by our
algorithm covers all the points. We can show that a small extension of these
balls, say $B_{i}^{\prime}$ for each $B_{i}$, has the property that they can
cover all the points (because even the original balls $B_{i}$ has this
property) and each such ball is assigned only slightly more than $U$ points.
Finally, we use a subtle matching based argument to show that the slightly
extra points in each of these extended balls $B_{i}^{\prime}$ can be covered
by a ball whose radius matches the radius of a unique small optimal ball. This
allows us to get a better 3-approximation algorithm, and our approach extends
to $L_{p}$ norm of cluster radii as well. Thus, we get the following result:

###### Theorem 1.1

There is a randomized $(3+\varepsilon)$-approximation algorithm for
Capacitated $k$-sumRadii with uniform capacities, where $\varepsilon>0$ is any
positive constant. For $p\geq 1$, there is a randomized
$(1+\varepsilon)(2^{2p-1}+1)^{1/p}$-approximation algorithm when the objective
function is the $L_{p}$ norm of the cluster radii. The expected running time
of both the algorithms is
$2^{O(k\log(k/\varepsilon))}\cdot{\mathsf{poly}}(n)$.

We now consider the general Capacitated $k$-sumRadii problem with non-uniform
capacities. Again, our initial steps are similar to those in [2] – we
initially guess the optimal cluster radii
$r_{1}^{\star},\ldots,r_{k}^{\star}$; and greedily find a set of balls
$B_{1},\ldots,B_{\ell}$, where $\ell\leq k$ and these balls cover the entire
set of points. Further, each of the balls $B_{i}$ is supposed to also contain
the corresponding optimal cluster $C_{i}^{\star}$. At this moment, we need to
find some more balls which can be used to satisfy the capacity constraints,
i.e., balls which are approximations to
$C_{\ell+1}^{\star},\ldots,C_{k}^{\star}$ respectively. Bandyopadhyay et al.
[2] approached this problem as follows: for an index $i\in[k]\setminus[\ell]$,
one can guess the the set of balls $B_{j},j\in[\ell]$ that intersect
$C^{\star}_{i}$. If any of these balls $B_{j}$ have smaller radius than
$r_{i}^{\star}$, we can use a enlarged version $B_{j}^{\prime}$ of $B_{j}$ to
cover $C^{\star}_{i}$ and treat this as the ball $B_{i}$. The radius of
$B_{j}^{\prime}$ can be charged to $r^{\star}_{i}$. Therefore, the non-trivial
case arises when $r_{i}^{\star}$ is much less than the radii of each of the
balls $B_{j}$ intersecting $C_{i}^{\star}$. In such a case, they realized that
$C_{i}^{\star}$ is contained in the intersection of the balls $B_{j}^{\prime}$
defined above. Therefore, they maintain a set of replacement balls, which are
mutually disjoint, and are supposed to contain at least the same number of
points as the corresponding cluster $C_{i}^{\star}$.

Ensuring that one can maintain such a collection of disjoint replacement balls
that are also disjoint with some desired subset of optimal balls turns out to
be non-trivial. In fact, we feel that the proof of Lemma 14 in [2], without a
non-trivial fix, has a technical flaw: while inserting a new replacement ball
in the set $\mathcal{B}_{2}$, it may happen that the replacement intersects
with an optimal ball with index in $\mathcal{I}_{2}$. 111 In the proof of
Lemma 14 in [2] (Lemma 2.5 in the arXiv version), the last line of the first
paragraph reads “If $B_{x}$ does not intersect any ball
$B_{i^{\prime}}^{\star}$ with $i^{\prime}\in[k]\setminus(I_{1}\cup I_{2})$,
then by the above discussion we have that setting $B_{i}=B_{x}$,
$(I_{1},I_{2}\cup\\{i\\},\mathcal{B}_{1},\mathcal{B}_{2}\cup\\{B_{i}\\})$ is a
valid configuration.” However, by doing so, one cannot rule out the
intersection of $B_{i}$ with a ball $B_{i^{\prime}}^{\star}$ with
$i^{\prime}\in I_{2}$, contradicting the fourth invariant property of a valid
configuration: “For every $i\in I_{2}$ and $s\notin I_{1}$, $B_{s}^{\star}$
and $B_{i}$ do not intersect.” It is tricky to note why this is the case. They
indeed rule out the intersection of $B_{i}^{\star}$ with any ball in
$\mathcal{B}_{2}$, but they do not ensure that $B_{i}$ does not intersect an
optimal ball $B_{s}^{\star}$ corresponding to the index $s\in I_{2}$.  Our
algorithm uses a more fine grained approach: we first identify a set $P_{j}$
of points which could contain the desired replacement ball (this step is also
there in [2]). Now we guess the set $Z$ of optimal clusters which could
intersect this candidate set $P_{j}$. The algorithm then runs over several
iterations, where in each iteration it shrinks the candidate set of points
$P_{j}$ containing the replacement ball, and hence the list $Z$ (see Algorithm
5). This process terminates when it either identifies a replacement ball or a
ball containing a cluster $C_{r}^{\star}$. To get a better approximation
ratio, we also maintain several set of balls with varying properties. We prove
the following result:

###### Theorem 1.2

There is a randomized $(4+\sqrt{13}+\varepsilon)$-approximation algorithm for
Capacitated $k$-sumRadii, where $\varepsilon>0$ is any positive constant. For
$p\geq 1$, there is a randomized $(4+\sqrt{13}+\varepsilon)$-approximation
algorithm when the objective function is the $L_{p}$ norm of the cluster
radii. The expected running time of both the algorithms is
$2^{O(k^{3}+k\log(k/\varepsilon))}\cdot{\mathsf{poly}}(n)$.

Our final result shows that the exponential dependence on running time is
necessary if we want a $c$-approximation algorithm, where $c$ is a constant
larger than 1. This result assumes that the Exponential Time Hypothesis holds
and uses a reduction from Vertex Cover on bounded degree graphs. A nearly
exponential time lower bound for approximating Vertex Cover on such graphs
follows from [8]. More formally, we have the following result:

###### Theorem 1.3

Assume that ETH holds. Then there exist positive constants $c_{1},c_{2}$,
where $c_{1}>1,$ such that any algorithm for Capacitated $k$-sumRadii with
running time at most $2^{c_{2}k/\mathsf{polylog}k}\cdot{\mathsf{poly}}(n)$
must have approximation ratio at least $c_{1}$.

###  1.2 Preliminaries

We define the Capacitated $k$-sumRadii problem. An instance ${\cal I}$ of this
problem is specified by a set of $n$ points $P$ in a metric space, a parameter
$k$ and capacities $U_{p}$ for each point $p\in P$. A solution to such an
instance needs to find a subset $C\subseteq P$, denoted “centers”, such that
$|C|=k$. Further, the solution assigns each point in $P$ to a unique center in
$C$ such that for any $c\in C$, the total number of points assigned to it is
at most its capacity $U_{c}$. It is worth noting that we are interested in the
so-called “hard” capacity version, where one cannot locate multiple centers at
the same point.

Assuming $C=\\{c_{1},\ldots,c_{k}\\}$, let $C_{j}$ denote the set of points
assigned to the center $c_{j}$ by this solution. We refer to $C_{j}$ as the
cluster corresponding to $C_{j}$ and define its radius $r_{j}$ as $\max_{p\in
P_{j}}d(p,c_{j})$. The goal is to find a solution for which the sum of cluster
radii is minimized, i.e., we wish to minimize $\sum_{j=1}^{k}r_{j}$. In the
$L_{p}$-norm version of this problem, the specification of an instance remains
as above, but the objective function is given by
$\left(\sum_{j=1}^{k}r_{j}^{p}\right)^{1/p}$. Given an instance ${\cal I}$ as
above, let ${\mathsf{OPT}}({\cal I})$ denote an optimal solution to ${\cal
I}$. Let $r^{\star}_{1},\ldots,r^{\star}_{k}$ be the radii of the $k$ clusters
in this optimal solution. By a standard argument, we can show that one can
guess close approximations to these radii.

###### Lemma 1

[2] Given a positive constant $\varepsilon>0$, there is an
$O(2^{O(k\log(k/\varepsilon))}\cdot n^{3})$ time algorithm that outputs a list
$\cal L$, where each element in the list is a sequence $(r_{1},\ldots,r_{k})$
of non-negative reals, such that the following property is satisfied: there is
a sequence $(r_{1},\ldots,r_{k})\in{\cal L}$ such that for all $j\in[k]$,
$r_{j}\geq r_{j}^{\star}$ and
$\sum_{j=1}^{k}r_{j}\leq(1+\varepsilon)\sum_{j=1}^{k}r_{j}^{\star}.$ Further,
the size of the list $\cal L$ is $O(2^{O(k\log(k/\varepsilon))}\cdot n^{2})$.

Given a point $x$ and non-negative value $r$, let $B(x,r)$ denote the ball of
radius $r$ around $x$, i.e., $B(x,r):=\\{p\in P:d(p,x)\leq r\\}$, where
$d(a,b)$ denote the distance between points $a$ and $b$. For a positive
integer $r$, we shall use $[r]$ to denote the set $\\{1,\ldots,r\\}$.

###  1.3 Related Work

In this section, we mention a few related research works on the sum-of-radii
problem that were not discussed earlier in the introduction. Note that most of
the work has been for the uncapacitated case. Behsaz and Salavatipour [4] give
an exact algorithm for the sum of radii problem in metrics induced by
unweighted graphs for the case when singleton clusters are disallowed.
Friggstad and Jamshidian [10] give a $3.389$-approximation algorithm for the
sum of radii problem in general metrics. This is an improvement over the
$3.504$ approximation of Charikar and Panigrahy [6], the first constant factor
approximation algorithm for this problem. Bandyapadhyay and Varadarajan [3]
discuss the variant of the problem where the objective function is the sum of
the $\alpha^{th}$ power of the radii. The algorithm can output
$(1+\varepsilon)k$ centers in the variant they study. Henzinger et al. [14]
give a constant approximation algorithm for metric spaces with bounded
doubling dimension in the dynamic setting where points can appear and
disappear. There also have been works for special metrics such as two-
dimensional geometric settings (e.g., [11]). The related problem of sum-of-
diameters has also been studied (e.g., [9, 4]).

We now give an outline of rest of the paper. In Section 2, we prove Theorem
1.1, i.e., we present an FPT approximation algorithm for Capacitated
$k$-sumRadii in the uniform capacity case. The more general non-uniform
capacity case is considered in Section 3, where we prove Theorem 1.2.

##  2 Uniform Capacities

In this section, we consider the special case of Capacitated $k$-sumRadii when
all the capacities $U_{p}$ are the same, say $U$. We give some notation first.
Fix an optimal solution $\mathcal{O}$ to an instance $\mathcal{I}$ given by a
set of $n$ points $P$. Let $c_{1}^{\star},\ldots,c_{k}^{\star}$ be the $k$
centers chosen by the optimal solution. For an index $j\in[k]$, let
$C_{j}^{\star}$ denote the set of points assigned to $c_{j}^{\star}$ by this
solution (i.e., the cluster corresponding to the center $c_{j}^{\star}$). Let
$r_{1}^{\star},\ldots,r_{k}^{\star}$ be the radii of the corresponding
clusters $C_{1}^{\star},\ldots,C_{k}^{\star}$. We also fix a parameter
$\gamma:=\frac{1}{k^{2}}$.

0.1 Input: Set $P$ of $n$ points, parameter $k,k_{L}^{\star}$, radii
$r_{1},\ldots,r_{k}$, capacity $U$.

0.2 Initialize a set $\mathcal{B}$ to empty.

0.3 Initialize an index set $I$ to $\\{1,\ldots,k_{L}^{\star}\\}$.

0.4 for  _$j=1,\ldots,k_{L}^{\star}$ _ do

0.5 Choose a point $c_{j}\in P$ uniformly at random.

0.6 Add $B_{j}:=B(c_{j},2r_{j})$ to $\mathcal{B}$ .

0.7while  _there is a point $x$ not covered by the balls in $\mathcal{B}$ _ do

0.8 (If $I=[k]$, output fail).

0.9 Choose an index $j\in[k]\setminus I$ uniformly at random.

0.10 Add $B_{j}:=B(x,2r_{j})$ to $\mathcal{B}$ and add $j$ to $I$ and define
$c_{j}:=x$.

0.11Initialize sets $T_{j}\subset[k],j\in I,$ to emptyset.

0.12 for  _each $i\in[k]\setminus I$ _ do

0.13 Choose an index $j\in I$ uniformly at random and add $i$ to $T_{j}$.

0.14Define $I^{\prime}:=\\{j\in I:|T_{j}|>0\\}$.

0.15 for  _each $j\in I$ _ do

0.16 if  _$j\in I^{\prime}$_ then

0.17 Define $B_{j}^{\prime}:=B(x,2r_{j}+2R_{j})$ and
$U_{j}^{\prime}:=U(1+\gamma)$, where $R_{j}:=\max_{i\in T_{j}}r_{i}$.

0.18 else

0.19 Define $B_{j}^{\prime}:=B_{j},U_{j}^{\prime}=U.$

0.20 Find disjoint subsets $G_{j}\subseteq B_{j}^{\prime}$ for each $j\in I$
such that $|G_{j}|\leq U_{j}^{\prime}$ and $P=\cup_{j}G_{j}$.

0.21 (terminate with failure if such subsets $G_{j}$ do not exist)

0.22 Let $I^{\prime\prime}\subseteq I^{\prime}$ be the index set consisting of
indices $j$ such that $|G_{j}|>U$.

0.23 Call Redistribute($\\{G_{j}:j\in I^{\prime\prime}\\},\\{c_{j}:j\in
I\\},\\{r_{j}:j\in[k_{L}]\\}$).

0.24 (terminate with failure if Redistribute outputs fail)

0.25 Let $\\{(w_{j},A_{j}):j\in I^{\prime\prime}\\}$ be the clustering
returned by Redistribute.

0.26 Output $\\{(c_{j},G_{j}):j\in I\setminus
I^{\prime\prime}\\}\cup\\{(c_{j},G_{j}\setminus A_{j}):j\in
I^{\prime\prime}\\}\cup\\{(w_{j},A_{j}):j\in I^{\prime\prime}\\}.$

Algorithm 1 An iteration of the algorithm for Capacitated $k$-sumRadii when
all capacities are $U$.

###### Definition 1

Call the optimal cluster $C_{j}^{\star}$ large if
$|C_{j}^{\star}|\geq\frac{\gamma U}{k}$; otherwise call it small. Let
$k_{L}^{\star}$ denote the number of large clusters in the optimal solution
$\mathcal{O}$.

Assume without loss of generality that the clusters
$C^{\star}_{1},\ldots,C^{\star}_{k_{L}^{\star}}$ are large (and the rest are
small). Using Lemma 1, we can assume that we know radii $r_{1},\ldots,r_{k}$
satisfying the condition that $r_{j}\geq r_{j}^{\star}$ for all $j\in[k]$ and
$\sum_{j}r_{j}\leq(1+\varepsilon)\sum_{j}r_{j}^{\star}$. By cycling over the
$k$ possible choices of $k_{L}^{\star}$, we can also assume that we know this
value. The algorithm is given in Algorithm 1. It begins by guessing the center
$c_{j}$ of each large optimal cluster $C_{j}^{\star}$ and defines $B_{j}$ as
the ball of radius $2r_{j}$ around $c_{j}$ (line 1). The intuition is that
$c_{j}$ may not be equal to the center $c_{j}^{\star}$ but will lie inside the
cluster $C_{j}^{\star}$ with reasonable probability, and in this case, the
ball $B_{j}$ will contain $C_{j}^{\star}$. Let us assume that this event
happens. Now the algorithm adds some more balls to the set $\mathcal{B}$ (that
maintains the set of balls constructed so far). Whenever there is a point $x$
that is not covered by the balls in $\mathcal{B}$, we guess the index $j$ of
the optimal cluster $C_{j}^{\star}$ containing $x$ (line 1). We add a ball of
radius $2r_{j}$ around $x$ to $\mathcal{B}$: again the intuition is that if
$x\in C_{j}^{\star}$, then this ball contains $C_{j}^{\star}$.

The index set $I$ maintains the set of indices $j$ for which we have
approximation to $C_{j}^{\star}$ in $\mathcal{B}$. At this moment, the set of
balls in $\mathcal{B}$ cover the point set $P$ but we are not done yet because
we need to assign points to balls while maintaining the capacity constraints.
Now, for each index $i\notin I$, we guess the index of a ball
$B_{j}\in\mathcal{B}$ such that $B_{j}$ intersects $C_{i}^{\star}$ (such a
ball must exist since the balls in $\mathcal{B}$ cover $P$, and in case there
are more than one candidates for $B_{j}$, we pick one arbitrarily). We add the
index $i$ to a set $T_{j}$ (line 1). Now we define $I^{\prime}$ as the subset
of $I$ consisting of those indices $j$ for which $T_{j}$ is non-empty (line
1). Now, for each $j\in I^{\prime}$, let $R_{j}$ denote the maximum radius of
any of the balls corresponding to $T_{j}$. We replace $B_{j}$ by a larger ball
$B_{j}^{\prime}$ by extending the radius of $B_{j}$ by $2R_{j}$ – this ensures
that $B_{j}^{\prime}$ contains $C_{i}^{\star}$ for any $i^{\star}\in T_{j}$.
Further we allow $B_{j}^{\prime}$ to have $U_{j}^{\prime}:=U(1+\gamma)$ points
assigned to it (line 1). For indices $j\in I\setminus I^{\prime}$, we retain
$B_{j}^{\prime},U_{j}^{\prime}$ as $B_{j},U_{j}$ respectively (line 1). Now,
we find a subset $G_{j}$ of each ball $B_{j}^{\prime}$ such that $|G_{j}|\leq
U_{j}^{\prime}$ and $\cup_{j}G_{j}$ covers all the points $P$ (line 1). We
shall show such a subset exists if all our guesses above our correct.
Otherwise we may not be able to find such sets $G_{j}$; and in this case the
iteration terminates with failure. The intuition is that one feasible choice
of $G_{j}$ is as follows: for each $j\in I\setminus I^{\prime}$,
$G_{j}:=C_{j}^{\star}$, whereas for an index $j\in I^{\prime}$, we set $G_{j}$
to be the union of $C_{j}^{\star}$ and all the clusters $C_{i}^{\star}$, where
$i\in T_{j}$. Since each small cluster has at most $\gamma U/k$ points, the
total number of points in the latter clusters is at most $\gamma U$. But we
had set $U_{j}^{\prime}$ to $(1+\gamma)U$. It is also easy to check that we
can find such sets $G_{j}$ by a simple $b$-matching formulation. Now we
consider those subsets $G_{j}$ for which $|G_{j}|>U$ (this can only happen if
$j\in I^{\prime}$) and let $I^{\prime\prime}$ denote the corresponding index
set (line 1). Finally, we call the procedure ${\bf Redistribute}$ in line 1 to
redistribute the points in $G_{j},j\in I^{\prime\prime}$ such that each such
set has at most $U$ points. Note that so far we have only constructed $|I|$
balls in $\mathcal{B}$ and we can still add $k-|I|$ extra balls. The procedure
${\bf Redistribute}$ returns these extra balls – we finally return these balls
and remove suitable points from $G_{j},j\in I^{\prime\prime}$ (line 1). We
shall show later that $|I^{\prime\prime}|$ is less than $k_{L}$. Again, note
that if our random choices were bad, it is possible that Redistribute returns
failure, in which case the iteration ends with failure.

0.1 Input: $(G_{1},\ldots,G_{h})$, where $G_{i}$’s are pair-wise disjoint
subsets of $P$, where $|G_{i}|>U$ for all $i$; a subset $C$ of $P$, and a set
$R=\\{r_{1},\ldots,r_{k_{L}}\\}$ of radii.

0.2 for  _each ordered subset $(r_{\sigma_{1}},\ldots,r_{\sigma_{h}})$ of $R$
_ do

0.3 Construct a bipartite graph $H=(V_{L},V_{R},E)$ as follows.

0.4 $V_{L}$ has one vertex $v_{i}$ for each $G_{i},i\in[h]$. $V_{R}$ is
defined as $P\setminus C$.

0.5 Add an edge $(v_{i},w),v_{i}\in V_{L},w\in V_{R},$ iff
$|B(w,r_{\sigma_{i}})\cap G_{i}|\geq\gamma U$.

0.6 if  _$H$ has a matching that matches all vertices in $V_{L}$ _ then

0.7 Suppose $v_{i}$ is matched with $w_{i}\in R$ for each $i\in[h]$.

0.8 Let $A_{i}$ be a subset of $B(w_{i},r_{\sigma_{i}})\cap G_{i}$ such that
$|A_{i}|=\gamma U$.

0.9 Return $\\{(w_{i},A_{i}):i\in[h]\\}$ (and end the procedure).

0.10

Return fail.

Algorithm 2 Algorithm Redistribute

We now describe the algorithm Redistribute in Algorithm 2. The procedure
receives three parameters: the first parameter is a class of subsets
$\\{G_{1},\ldots,G_{h}\\}$ which are mutually disjoint. These correspond to
the sets $G_{i},i\in I^{\prime\prime}$ constructed in Algorithm 1 (and hence
$h=|I^{\prime\prime}|).$ The second parameter is a set $C$, which corresponds
to the set of centers chosen by Algorithm 1 (till the call to this procedure)
and the third parameter is a set of radii $\\{r_{1},\ldots,r_{k_{L}}\\}$ which
correspond to the radii of the large clusters. We shall ensure that $k_{L}\geq
h$. Recall that the goal is to identify balls which can take away $\gamma U$
points from each of the sets $G_{i}$. The radii of these balls shall come from
the set $R:=\\{r_{1},\ldots,r_{k_{L}}\\}$, and we shall show that we can
associate a unique radius with each of the desired balls. Thus, the procedure
tries out all ordered subsets of size $h$ of $R$ (line 2). For each such
ordered subset $(r_{\sigma_{1}},\ldots,r_{\sigma_{h}})$, we try to remove
$\gamma U$ points from each subset $G_{i}$ by using a suitable ball of radius
$r_{\sigma_{i}}$. Thus, we construct a bipartite matching instance as follows:
the left side has one vertex for each subset $G_{i}$ and the right side has
one vertex for each potential center of a ball (line 2). Now, we add an edge
between a vertex $v_{i}$ corresponding to $G_{i}$ on left and a vertex $w$ on
the right side if $G_{i}\cap B(w,r_{\sigma_{i}})$ has size at least $\gamma U$
(line 2). If this graph has a perfect matching, then we identify the desired
subsets $A_{i}\subseteq G_{i}$ of size $\gamma U$ (line 2) and return these.

###  2.1 Analysis

In this section, we prove correctness of the algorithm. We shall show that
with non-zero probability the algorithm outputs a 3-approximate solution. We
first define the set of desirable events during the random choices made by
Algorithm 1:

  * •

${\cal E}_{1}$: For each $j\in[k_{L}^{\star}]$, the point $c_{j}$ chosen in
line 1 of Algorithm 1 belongs to the cluster $C_{j}^{\star}$.

  * •

${\cal E}_{2}$: For each point $x$ chosen in line 1 of Algorithm 1, the index
$j$ chosen in line 1 satisfies the property that $x\in B_{j}^{\star}$.
Further, the algorithm does not output fail in line 1.

  * •

${\cal E}_{3}$: For each index $i$ considered in line 1 in Algorithm 1, the
index $j\in I$ selected in line 1 satisfies the property that $B_{j}\cap
B_{i}^{\star}$ is non-empty.

  * •

${\cal E}_{4}$: The set of centers $\\{c_{j}:j\in I\\}$ selected by Algorithm
1 is disjoint from the set of optimal centers of the large balls, i.e.,
$\\{c_{j}^{\star}:j\in[k_{L}^{\star}]\\}.$

We first show that all of these desirable events happen with non-zero
probability.

###### Lemma 2

Assuming $n\geq 2k^{5}$, all the events ${\cal E}_{1},{\cal E}_{2},{\cal
E}_{3},{\cal E}_{4}$ together happen with probability at least
$\frac{1}{k^{O(k)}}.$

###### Proof

We first check event ${\cal E}_{4}\cap{\cal E}_{1}$. Consider an iteration $j$
of the for loop in line 1. Conditioned on the choices in the previous $j-1$
iterations, the probability that $c_{j}\in
C_{j}^{\star}\setminus\\{c_{j}^{\star}:j\in[k_{L}^{\star}]\\}$ is at least
$\frac{|C_{j}^{\star}|-k}{n}$. Since $C_{j}^{\star}$ is large, we know that
$|C_{j}^{\star}|\geq\gamma U/k\geq n/k^{4}$ (since $\gamma=1/k^{2}$ and $U\geq
n/k$). Using the fact that $n\geq 2k^{5}$, we get

$\Pr[{\cal E}_{1}\cap{\cal E}_{4}]=\Pr[c_{j}\in
C_{j}^{\star}\setminus\\{c_{j}^{\star}:j\in[k_{L}^{\star}]\\},\text{for all
$j=1,\ldots,k_{L}^{\star}$}]\geq\left(\frac{1}{2k^{4}}\right)^{k}=\frac{1}{2^{k}k^{4k}}$

Now we consider ${\cal E}_{2}$. We condition on the coin tosses before the
while loop in line 1 such that ${\cal E}_{1}\cap{\cal E}_{4}$ occur. This
implies that for every $j\in[k_{L}^{\star}]$, $C_{j}^{\star}\subseteq B_{j}$.

The probability that we correctly guess the index $j$ such that the cluster
$C_{j}^{\star}$ contains $x$ (in line 1) is $1/k$. Since there can be at most
$k$ iterations of the while loop, the probability that this guess is correct
for each point $x$ chosen in line 1 is at least $1/k^{k}$. Further, if this
guess is always correct, then $B_{j}$ contains $C_{j}^{\star}$ for all $j\in
I$. This shows that if $I$ becomes equal to $[k]$, then the balls $B_{j}$
would cover $P$ and hence, we won’t output fail. Thus, we see that

$\Pr[{\cal E}_{2}|{\cal E}_{1}\cap{\cal E}_{4}]\geq 1/k^{k}.$

Finally we consider ${\cal E}_{3}$. Again condition on the events before the
for loop in line 1 and assume that ${\cal E}_{1}\cap{\cal E}_{2}\cap{\cal
E}_{4}$ occur. There are at most $k$ iterations of the ${\bf for}$ loop. Since
$\cup_{j\in I}B_{j}=P$, there must exist an index $j\in I$ such that $B_{j}$
intersects $C_{i}^{\star}$. Therefore, the probability that we guess such an
index $j$ in line 1 is at least $1/k$. Thus, we get

$\Pr[{\cal E}_{3}|{\cal E}_{1}\cap{\cal E}_{2}\cap{\cal E}_{4}]\geq 1/k^{k}.$

Combining the above inequalities, we see that $\Pr[{\cal E}_{1}\cap{\cal
E}_{2}\cap{\cal E}_{3}\cap{\cal E}_{4}]\geq\frac{1}{2^{k}k^{6k}}.$ This
implies the desired result.

We now show that the sets $G_{j}$ as required in line 1 exist and can be found
efficiently.

###### Claim

Assume that the events ${\cal E}_{1},\ldots,{\cal E}_{4}$ occur. Let
$B_{j}^{\prime},U_{j}^{\prime}$ be as defined in lines 1–1 of Algorithm 1.
Then there exist mutually disjoint subsets $G_{j}\subseteq B_{j}^{\prime}$ for
each $j\in I$ such that $P=\cup_{j\in I}G_{j}$ and $|G_{j}|\leq
U_{j}^{\prime}$ for each $j\in I$. Further, the subsets $G_{j}$ can be found
in ${\mathsf{poly}}(n)$ time.

###### Proof

Since events ${\cal E}_{1},{\cal E}_{2},{\cal E}_{3}$ occur, it is easy to
check that for each $j\in I$, $B_{j}^{\prime}$ contains
$C_{j}^{\star}\cup\bigcup_{h\in T_{j}}C_{h}^{\star}$. Further, if $T_{j}$ is
non-empty, then

$|C_{j}^{\star}|+\sum_{h\in T_{j}}|C_{h}^{\star}|\leq U(1+\gamma),$

because each of the clusters $C_{h}^{\star}$ is small. Thus, one feasible
choice for the subsets $G_{j}$ is as follows: for each $j\in I$ such that
$T_{j}$ is empty, define $G_{j}=C_{j}^{\star}$, otherwise define
$G_{j}=C_{j}^{\star}\cup\bigcup_{h\in T_{j}}C_{h}^{\star}$. This proves the
existence of the desired subsets $G_{j}$. It is easy to check that such a
collection of subsets can be found by standard flow-based techniques, and
hence, would take ${\mathsf{poly}}(n)$ time.

We now show that the Redistribute outputs the desired subsets.

###### Lemma 3

Assume that the events ${\cal E}_{1},\ldots,{\cal E}_{4}$ occur. Then
Algorithm 2 does not fail.

###### Proof

We first consider the following bipartite graph
$H^{\prime}=(V_{L}^{\prime},V_{R}^{\prime},E^{\prime})$ (this is for the
purpose of analysis only): the vertex set $V_{L}^{\prime}$ has one vertex
$v_{i}$ for each of subsets $G_{i}$, and hence, is same as the set $V_{L}$
considered in line 2 of Algorithm 2. $V_{R}^{\prime}$ has a vertex $w_{j}$ for
each optimal cluster $C_{j}^{\star},j\in k_{L}^{\star}$. We add an edge
$(v_{i},w_{j})$ iff $|G_{i}\cap C_{j}^{\star}|\geq\gamma U$. We claim that
there is a matching in this graph that matches all the vertices in
$V_{L}^{\prime}$. Suppose not. Then there is a subset $X$ of $V_{L}^{\prime}$
such that $|N(X)|<|X|$, where $N(X)$ denotes the neighborhood of $X$. Now,

$\displaystyle\sum_{i\in X}|G_{i}|$ $\displaystyle=\sum_{i\in
X}\sum_{j\in[k]}|C_{j}^{\star}\cap G_{i}|=\sum_{j\in[k]}\sum_{i\in
X}|C_{j}^{\star}\cap G_{i}|$ $\displaystyle\leq\sum_{j\in
N(X)}|C_{j}^{\star}|+\sum_{j\in[k]\setminus N(X)}\sum_{i\in X}\gamma U$
$\displaystyle\leq|N(X)|U+k^{2}\gamma U$ $\displaystyle\leq U(|X|-1)+U=U|X|,$

where the second inequality uses the fact that if $i\in[k]\setminus N(X)$,
then $|C_{j}^{\star}\cap G_{i}|\leq\gamma U$. Indeed, if $C_{j}^{\star}$ is
small, this follows from the observation that $|C_{j}^{\star}|\leq\gamma U$.
Otherwise, $j\in[k_{L}^{\star}]$ and hence we have a vertex $w_{j}$
corresponding to $C_{j}^{\star}$ in $H^{\prime}$. Since $(v_{i},w_{j})$ is not
an edge in $H^{\prime}$, it follows that $C_{j}^{\star}\cap G_{i}$ has size at
most $\gamma U$. Now we get a contradiction because for each $i$, $|G_{i}|>U$
and hence, $\sum_{i\in X}|G_{i}|>U|X|$

Thus we have shown that $H^{\prime}$ has a matching that matches all the
vertices in $V_{L}^{\prime}$ – let $w_{\sigma_{i}}$ be the vertex in
$V_{R}^{\prime}$ which is matched to $v_{i}\in V_{L}^{\prime}$ by this
matching. Now consider the iteration of the for loop in line 2 in Algorithm 2
where the sequence of radii is given by
$(r_{\sigma_{1}},\ldots,r_{\sigma_{h}})$. We claim that the graph $H$
constructed in this iteration (in line 2) has a matching that matches all the
vertices in $V_{L}$. Indeed, we can match the vertex $v_{i}\in L$ with
$c_{\sigma_{i}}^{\star}$ because $\gamma U\leq|G_{i}\cap
C_{\sigma_{i}}^{\star}|\leq|G_{i}\cap
B(c_{\sigma_{i}}^{\star},r_{\sigma_{i}})|$ – we use the fact that the event
${\cal E}_{4}$ occurred, and hence, $c_{\sigma_{i}}^{\star}\in C$.

Now, let $M$ be the matching found in line 2 and suppose $v_{i}$ is matched
with a vertex $w_{i}\in R$. By definition of $H$, $B(w_{i},r_{\sigma_{i}})\cap
G_{i}$ has size at least $\gamma U$. Thus, we can find the desired subset
$A_{i}$ in line 2. Note that the subsets $A_{i}$ are mutually disjoint since
the sets $G_{i}$ are mutually disjoint. Further the points $w_{i},i\in H,$ are
also distinct since $M$ is a matching. Thus, the procedure ${\bf
Redistribute}$ returns $h$ clusters, each containing $\gamma U$ points.

It follows from the results above that the set of $k$ clusters returned by
Algorithm 1 in line 1 cover all the points in $P$ and satisfy the capacity
constraints. We now consider the objective function value of this solution.

###### Lemma 4

Assume that the events ${\cal E}_{1},\ldots,{\cal E}_{4}$ occur. Then the
total sum of the radii of the clusters returned by Algorithm 1 is at most
$3\sum_{j\in[k]}r_{j}$. Further, for any $p\geq 1$, the total $L_{p}$ norm of
the radii of the clusters returned by this algorithm is at most
$(2^{2p-1}+1)^{1/p}\left(\sum_{j\in[k]}r_{j}^{p}\right)^{1/p}.$

###### Proof

For each $j\in I$, the ball $B_{j}$ constructed during lines 1–1 has radius at
most $2r_{j}$. Now, the ball $B_{j}^{\prime}$ constructed during the for loop
in line 1 has radius at $2r_{j}+\sum_{h\in T_{j}}2r_{h}$. Therefore, the total
radii of the balls in $B_{j}^{\prime}$ is at most

$\sum_{j\in I}\left(2r_{j}+\sum_{h\in T_{j}}2r_{h}\right)\leq
2\sum_{j\in[k]}r_{j},$

where the inequality follows from the fact that sets $\\{j\\}\cup T_{j},$
where $j\in I$, are mutually disjoint. Finally, the total sum of the radii of
the sets $A_{i}$ returned by Redistribute is at most $\sum_{j\in[k]}r_{j}$.
This proves the first statement in the Lemma.

Further, the $L_{p}$-norm of the radii of the clusters output by this
algorithm is at most

$\sum_{j\in
I}(2r_{j}+2R_{j})^{p}+\sum_{j\in[k]}r_{j}^{p}\leq\sum_{j\in[k]}2^{2p-1}r_{j}^{p}+\sum_{j\in[k]}r_{j}^{p},$

where $R_{j}$ is as defined in line 1 of Algorithm 1. This completes the proof
of the desired result.

Thus, with probability at least $1/k^{O(k)}$ (Lemma 2), Algorithm 1 outputs a
feasible solution with approximation guarantees as given by Lemma 4. Repeating
Algorithm 1 $k^{O(k)}$ times and using Lemma 1 yields Theorem 1.1.

##  3 Non uniform capacities

In this section, we consider the general case of Capacitated $k$-sumRadii when
points can have varying capacities. Recall that for a point $p$, $U_{p}$
denotes the capacity of $p$. We first give an informal description of the
algorithm. Let $r_{1}^{\star},\ldots,r_{k}^{\star}$ denote the radii of the
$k$ optimal clusters $C_{1}^{\star},\ldots,C_{k}^{\star}$. Let
$c_{1}^{\star},\ldots,c_{k}^{\star}$ be the centers of these clusters
respectively. Let $B_{j}^{\star}$ denote the ball
$B(c_{j}^{\star},r_{j}^{\star})$ – note that $C_{j}^{\star}\subseteq
B_{j}^{\star}$. As in the case of uniform capacities (Section 2), we begin by
assuming that we know radii $r_{1},\ldots,r_{k}$ satisfying the conditions of
Lemma 1, i.e., $r_{j}\geq r_{j}^{\star}$ and
$\sum_{j=1}^{k}r_{j}\leq(1+\varepsilon)\sum_{j=1}^{k}r_{j}^{\star}$, where
$\varepsilon>0$ is an arbitrarily small constant.

Our algorithm maintains three subsets of balls, namely
$\mathcal{B}_{1},\mathcal{B}_{2},\mathcal{B}_{3}$. Each ball in these sets
corresponds (in a sense that we shall make clear later) to a unique optimal
ball $B_{j}^{\star}$. Thus we denote balls in
$\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\mathcal{B}_{3}$ as $B_{j}$, where the
index $j$ denotes the fact that $B_{j}$ corresponds to $B_{j}^{\star}$.
Further, we use $c_{j}$ to denote the center of $B_{j}$. We maintain three
sets of (mutually disjoint) indices $I_{1},I_{2},I_{3}\subseteq[k]$
respectively. We also maintain an index set $I_{4}:=[k]\setminus(I_{1}\cup
I_{2}\cup I_{3})$ denoting those indices for which we have not assigned a ball
yet.

The set $\mathcal{B}_{1}$ is obtained by the following greedy procedure: while
there are points not covered by the balls in $\mathcal{B}_{1}$, we pick an
uncovered point $p$, guess the index of the optimal cluster covering it, say
$j$, and add the ball $B(c_{j},3r_{j})$ to $\mathcal{B}_{1}$, where $c_{j}$ is
a high capacity point close to $p$ (the actual process is slightly nuanced,
but the details will be clarified in the actual algorithm description). When
this process ends, we have a set of balls covering $P$ such that each ball in
$\mathcal{B}_{1}$ covers a corresponding (unique) optimal ball. The set
$\mathcal{B}_{1}$ remains unchanged during rest of the algorithm. We now need
to add more balls to this solution in order to satisfy the capacity
constraints.

Such balls shall be added to the sets $\mathcal{B}_{2}$ and $\mathcal{B}_{3}$
respectively (and the index sets $I_{2}$ and $I_{3}$ shall maintain the
correspondence with unique clusters in the optimal solution respectively).
Roughly, a ball $B_{j}\in\mathcal{B}_{2}$ of the form $B(c_{j},r)$ shall
satisfy the condition that $r\leq 5r_{j}$ and $B^{\star}_{j}\subseteq B_{j}$.
Our algorithm shall never remove a ball that once gets added to
$\mathcal{B}_{2}$. A typical setting when we can add a ball to
$\mathcal{B}_{2}$ is the following: Suppose there is an index $j\in I_{4}$
such that the optimal ball $B_{j}^{\star}$ intersects a ball
$B_{h}\in\mathcal{B}_{1}\cup\mathcal{B}_{2}$ and $r_{j}$ is at least the
radius of $B_{h}$ (we do not know this fact a priori, but our algorithm can
guess such cases). In this case, we find a high capacity point $x$ in the
vicinity of $c_{h}$, such that $B_{j}=B(x,5r_{j})$ covers $B_{j}^{\star}$.

A ball $B_{j}$ added to the set $\mathcal{B}_{3}$ shall have the property that
it does not intersect any of the balls $B^{\star}_{h},h\in I_{3}\cup I_{4}$
(again, we cannot be certain here since we do not know the optimal balls, but
we shall show that in one of the cases guessed by our algorithm, this
invariant will be satisfied). A ball $B_{j}$ once added to $\mathcal{B}_{3}$
can get deleted, but in this case we will add a corresponding ball to
$\mathcal{B}_{2}$, i.e., we shall remove the index $j$ from $I_{3}$ and add it
to $I_{2}$. This can happen because of the following reason: suppose we have
identified a ball $B_{h},h\in I_{4}$ (centered around a point $c_{h}$), that
we want to add to $\mathcal{B}_{3}$. But it intersects the optimal ball
$B_{j}^{\star}$ for an index $j\in I_{3}$ (again, we guess this fact). Now if
$r_{j}\geq r_{h}$, it follows that, as before, we can find a high capacity
point $x$ in the vicinity of $c_{h}$ such that $B_{j}=B(x,5r_{j})$ covers
$B_{j}^{\star}$.

Identifying a ball which gets added to $\mathcal{B}_{3}$ is at the heart of
our technical contribution. Essentially we start with a suitable ball $B$
(picked from a certain set of possibilities) which we would like to add to
$\mathcal{B}_{3}$. As long as there is an optimal ball $B_{j}^{\star},j\in
I_{3}\cup I_{4}$ intersecting $B$, we able transfer an index from $I_{3}$ to
$I_{2}$ or suitably shrink the possibilities for identifying the ball $B$.

We mention one final technicality. For each ball $B_{j}\in\mathcal{B}_{3}$
maintained by the algorithm, we shall maintain a subset $C_{j}$. The subset
$C_{j}$ is meant to capture the subset of points that will be actually be part
of the $j^{th}$ cluster output by the algorithm (although the final output may
be a subset of $C_{j}$). The reason for this is as follows. We would like to
maintain the following invariant during the algorithm:

  * Invariant 1: Let $j,j^{\prime}\in I_{3}$ be two distinct indices. Then $C_{j}\cap C_{j^{\prime}}=\emptyset$. Further, for any $j\in I_{3}$ and $i\in I_{3}\cup I_{4},$ $B_{i}^{\star}\cap C_{j}=\emptyset.$

###  3.1 Algorithm Description

We now give a formal description of our algorithm for Capacitated $k$-sumRadii
in Algorithm 4. Here we describe one iteration of the algorithm and shall show
that it outputs the desired solution with probability at least
$\frac{1}{2^{O(k^{3})}}.$ As mentioned above, there are three sets of balls
$\mathcal{B}_{1},\mathcal{B}_{2},\mathcal{B}_{3}$ and corresponding (mutually
disjoint) index sets $I_{1},I_{2},I_{3}$. The set $I_{4}$ which is initialized
to $[k]$ stores the index sets for which we haven’t added a ball in
$\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\mathcal{B}_{3}$.

We first explain a subroutine that we shall be using repeatedly during the
algorithm:
InsertBall($p,j,r,u)$). Here $u$ is an index in $\\{1,2,3\\}$. The procedure
is supposed to insert the ball $B(p,r)$ centered at $p$ to the set
$\mathcal{B}_{u}$ (and add the index $j$ to $I_{u}$ – the index $j$ before
this step lies in $I_{4}$, the set of unused indices). However, there is a
caveat – we want to avoid the case when $p$ happens to be same as the optimal
center $c_{h}^{\star}$ for some other $h\neq j$. The reason is that in a
subsequent step, the algorithm may try to insert a ball that is an
approximation of $B_{h}^{\star}$. At this moment, it may happen that
$c_{h}^{\star}$ is the only feasible choice for a center because all other
points close to $c_{h}^{\star}$ have very low capacity. Therefore, the
procedure InsertBall needs to check if this is the case. In particular, it
guesses this fact, and if indeed $p$ happens to be same as $c_{h}^{\star}$, it
places a ball of radius $r_{h}$ around $c_{h}^{\star}$ in $\mathcal{B}_{1}$.
The algorithm maintains a global index set $I^{\star}$ consisting of those
indices $j$ for which it has executed this step, i.e., for which the center of
the corresponding ball $B_{j}\in\mathcal{B}_{1}$ is same as $c_{j}^{\star}$.
Note that $I^{\star}$ is a subset of $I_{1}$. Whenever it adds such an index
to $I^{\star}$, it sets $I_{1}$ to $I^{\star}$, $\mathcal{B}_{1}$ to
$\\{B(c_{i},r_{i}),i\in I^{\star}\\}$ and resets
$I_{2},I_{3},\mathcal{B}_{2},\mathcal{B}_{3}$ to empty (see line 3 in
Algorithm 3), and then restarts the Algorithm 4 from line 4

For sake of clarity of the algorithm, we shall always assume that the choice
among the two options (i) and (ii) taken by this algorithm is correct, and
also that whenever the algorithm chooses option (ii), it chooses $h$,
satisfying $p=c_{h}^{\star}$. The reason is that we will later see that this
procedure is called $O(k^{2})$ times, and it chooses the option (ii) at most
$k$ times. Hence, the probability that procedure makes the correct choices
each time is $1/2^{O(k^{2})}$, which suffices for our purpose.

0.1 Input: Candidate center $p$, radius $r$, index $j\in I_{4}$, index
$u\in\\{1,2,3\\}.$

0.2 Perform one of the following two steps with equal probability:

0.3 (i) Add the ball $B(p,r)$ to $\mathcal{B}_{u}$ and the index $j$ to
$I_{u}$ (and remove $j$ from $I_{4}$). Set $c_{j}=p$.

0.4 (ii) Guess an index $h\in[k]\setminus I^{*}$ uniformly at random. Set
$c_{h}=p$.

0.5 set $I_{2},I_{3},\mathcal{B}_{2},\mathcal{B}_{3}$ to empty.

0.6 Add $h$ to $I^{\star}$

0.7 Set $I_{1}=I^{\star}$ and $\mathcal{B}_{1}=\\{B(c_{i},r_{i}),i\in
I^{\star}\\}$

Go to line 4 of Algorithm 3

Algorithm 3 The procedure InsertBall($p,j,r,u)$).

We now describe Algorithm 3.

In lines 4–4, we add balls to $\mathcal{B}_{1}$ whose union covers $P$. Each
such ball $B_{j}$, corresponding to an index $j$ (which is maintained in the
index set $I_{1}$), is supposed to contain the optimal ball $B_{j}^{\star}$.
Further, the center $c_{j}$ of $B_{j}$ should have capacity at least that of
$c_{j}^{\star}$. In each iteration of this while loop, we first pick an
uncovered point $p$ and guess the index $j$ such that $p\in C_{j}^{\star}$
(line 4). We now find the highest capacity point $x\in B(p,r_{j})$ (while
avoiding the centers already chosen). We now call InsertBall$(x,j,3r_{j},1)$,
i.e., we would like to insert the ball $B(x,3r_{j})$ to $\mathcal{B}_{1}$.

In an iteration during lines 4–4, we add one ball to our solution for a
remaining index $j\in I_{4}$. In particular, we pick the index $j\in I_{4}$
with the highest radius $r_{j}$ (line 4) and guess a random subset $T_{j}$ of
$I_{1}\cup I_{2}$ (line 4). The set $T_{j}$ is supposed to denote the indices
$h\in I_{1}\cup I_{2}$ such that the ball $B_{h}$ intersects the optimal ball
$B_{j}^{\star}$. Assume that the algorithm guesses the set $T_{j}$ correctly
(which again happens with probability at least $\frac{1}{2^{k}}$). Now two
cases arise: (i) The radius $r_{j}$ is at least the radius of some ball
$B_{h},h\in T_{j}$, (ii) The radius $r_{j}$ is less than the latter quantity
for all $h\in T_{j}$. Note that ${\mathsf{radius}}(B_{h})$ is either $3r_{h}$
(when $h\in I_{1}$) or $5r_{h}$ (when $h\in I_{2}$).

In the first case (line 4), we identify a ball $B_{j}$ containing
$B_{j}^{\star}$. Let $h$ be the index in $T_{j}$ such that $r_{j}$ is at least
${\mathsf{radius}}(B_{h})$. We find the highest capacity point $x\in
B(c_{h},{\mathsf{radius}}(B_{h})+r_{j})$ (line 4) except the already chosen
centers – since $B_{h}$ intersects $B_{j}^{\star}$, we note that
$c_{j}^{\star}$ is a possible candidates for the point $x$, and hence
$U_{x}\geq U_{c_{j}^{\star}}$ Finally, we add the ball $B_{j}=B(x,5r_{j})$ to
$\mathcal{B}_{2}$ (line 4). It is not difficult to show that $B_{j}$ contains
$B_{j}^{\star}$. The second case, when $r_{j}<{\mathsf{radius}}(B_{h})$ for
all $h\in T_{j}$, is more challenging. We first identify a candidate set of
points $P_{j}$ which contain the optimal ball $B_{j}^{\star}$ (line 4) and
then prune enough points from it to identify a ball $B_{j}$. For each $h\in
T_{j}$ (line 4), we define an extended ball $E_{h}$ of radius $9r_{h}$ around
$c_{h}$ (clearly, $E_{h}$ contains the ball $B_{h}$, which is of radius either
$3r_{h}$ or $5r_{h}$ around $c_{h}$). We shall show later $E_{h}$ contains
$B_{j}^{\star}$. Thus, $B_{j}^{\star}\subseteq\bigcap_{h\in T_{j}}E_{h}$. By
our assumption on the correct guess of the set $T_{j}$, it follows that
$B_{i}\cap B_{j}^{\star}$ is empty for $i\in(I_{1}\cup I_{2})\setminus T_{j}$
Further, Invariant 1 implies that for any subset $C_{i}$ in $\mathcal{B}_{3}$,
$i\in I_{3}$, $B_{j}^{\star}\cap C_{i}$ is empty. Thus, the set $P_{j}$ as
defined in line 4 contains $B_{j}^{\star}$. We now call the subroutine
UpdateBalls to add a suitable ball corresponding to $B_{j}^{\star}$ to
$\mathcal{B}_{3}$ (or move a ball from $\mathcal{B}_{3}$ to
$\mathcal{B}_{2}$).

0.1 Input: Set $P$ of $n$ points, parameter $k,$ radii $r_{1},\ldots,r_{k}$,
capacities $U_{p}$ for each point $p\in P$.

0.2 Initialize $I_{1},I_{2},I_{3}$ to emptyset and $I_{4}$ to $[k].$

0.3 Initialize the sets $\mathcal{B}_{1},\mathcal{B}_{3},\mathcal{B}_{3}$ to
emptyset.

0.4 while  _the balls in $\mathcal{B}_{1}$ do not cover $P$ _ do

0.5 Pick a point $p\in P\setminus\left(\bigcup_{j\in I_{1}}B_{j}\right)$.

0.6 (Output fail if $I_{4}$ is empty).

0.7 Choose $j\in I_{4}$ uniformly at random.

0.8 Let $x$ be the highest capacity point in $\left(P\setminus\\{c_{i}:i\in
I_{1}\\}\right)\cap B(p,r_{j}).$

0.9 Call InsertBall$(x,j,3r_{j},1)$

0.10while  _$I_{4}$ is non-empty _ do

0.11 Let $j\in I_{4}$ with the highest $r_{j}$ value.

0.12 Choose a random subset $T_{j}\subseteq I_{1}\cup I_{2}$.

0.13 if  _there is an index $h\in T_{j}$ with
$r_{j}\geq{\mathsf{radius}}(B_{h})$ _ then

0.14 Let $x$ be the highest capacity point (other than $\\{c_{i}:i\notin
I_{4}\\}$) in $B(c_{h},{\mathsf{radius}}(B_{h})+r_{j})$.

0.15 Call InsertBall($x,j,5r_{j},2$).

0.16

0.17 else

0.18 For an index $h\in T_{j}$, define $E_{h}:=B(c_{h},9r_{h})$.

0.19 Define $P_{j}:=\left(\bigcap_{h\in
T_{j}}E_{h}\right)\setminus\left(\bigcup_{i\in(I_{1}\cup I_{2})\setminus
T_{j}}B_{i}\cup\bigcup_{i\in I_{3}}C_{i}\right).$

0.20 Call UpdateBalls($j,P_{j}$).

0.21

Output the balls $\\{B(c_{j},9r_{j}):j\in[k]\\}$

Algorithm 4 An iteration of the algorithm for Capacitated $k$-sumRadii for
general capacities.

We now give details of the UpdateBalls procedure. We also emphasize that this
is step where the technical novelty of our contribution lies. We assume that
the sets $I_{1},\ldots,I_{4}$, radii $r_{1},\ldots,r_{k}$ and
$\mathcal{B}_{1},\ldots,\mathcal{B}_{3}$ can be accessed or modified by this
procedure. The parameters given to this procedure are an index $j\in I_{4}$
and a set $P_{j}$ of points which should contain the optimal ball
$B_{j}^{\star}$. The procedure can terminate in the following manner: (i) find
an index $i\in I_{3}$ and a ball containing $B_{i}^{\star}$ – in this case, we
move $i$ from $I_{3}$ to $I_{2}$ (and change $\mathcal{B}_{2},\mathcal{B}_{3}$
accordingly), or (ii) corresponding to the index $j$, add a ball $B_{j}$ and a
subset $C_{j}\subseteq B_{j}$ to $\mathcal{B}_{3}$. Note that Invariant 1
requires that $C_{j}$ should be disjoint from $B_{i}^{\star}$ for all $i\in
I_{3}\cup I_{4}$. Therefore the algorithm maintains a set $Z$ (initialized to
$I_{3}\cup I_{4}$) of indices that could potentially intersect the intended
ball $B_{j}$ (line 5). The set $Z$ gets pruned as we run through the
iterations of the while loop (lines 5–5). We now describe each iteration of
this while loop. In line 5, we identify a point $x$ of a high capacity such
that $B(x,r_{j})$ has a large intersection with $P_{j}$; and we let $C_{j}$
denote this intersection. Now, we guess the subset $L$ of $Z$ consisting of
the indices $i\in Z$ such that $B_{i}^{\star}\cap C_{j}$ is not empty (line
5). Assume that this guess is correct. If $L$ is empty (line 5), we can add
$B_{j}$ to $\mathcal{B}_{3}$. The procedure terminates in this case.

Hence assume that the set $L$ is not empty. There are two sub-cases now. In
the first sub-case (line 5), there is an index $t\in L$ such that
$r_{t}>r_{j}$. We shall show that $t\in I_{3}$ (recall that $L$ is a subset of
$I_{3}\cup I_{4}$). Since $B_{j}$ and $B_{t}^{\star}$ intersect, the ball
$B(x,r_{t}+r_{j})$ contains $c_{t}^{\star}$. Thus, we pick a high capacity
point $y$ in this ball (line 5) and add the ball $B(y,5r_{t})$ to
$\mathcal{B}_{2}$ (line 5) – the fact that $r_{t}>r_{j}$ ensures that this
ball contains $B_{t}^{\star}$. Thus, the index $t$ moves from $I_{3}$ to
$I_{2}$. The procedure terminates in this sub-case.

Finally, consider the sub-case when the set $L$ is non-empty and every index
$t\in L$ satisfies $r_{t}\leq r_{j}$. In line 5, we guess whether the ball
$B_{j}^{\prime}:=B(x,3r_{j})$ intersects $B_{j}^{\star}$. Assume that this
guess is correct. If $B_{j}^{\prime}\cap B_{j}^{\star}$ is non-empty (line 5),
then it is easy to see that the ball $B(x,5r_{j})$ contains $B_{j}^{\star}$.
Thus, we add this ball to $\mathcal{B}_{2}$ and terminate. Otherwise, we can
remove $B_{j}$ from $P_{j}$ (recall that $P_{j}$ contains a subset of points
which are guaranteed to contain $B_{j}^{\star}$). Now that $P_{j}$ has shrunk
(and hence, the possible set of points in the desired ball $B_{j}$ also
reduces), we can update the set $Z$. Recall that $Z$ stores indices $i\in
I_{3}\cup I_{4}$ such that $B_{i}^{\star}$ potentially intersects
$B_{j}^{\star}$. Since $r_{t}\leq r_{j}$ and $B_{t}^{\star}$ intersects
$B(x,r_{j})$ for all $t\in L$, it follows that $B_{t}^{\star}\subseteq
B_{j}^{\prime}$. Thus, $B_{t}^{\star}$ does not intersect the updated set
$P_{j}$. Thus, we can remove the $L$ from $Z$ (line 5). This is the only sub-
case where we perform another iteration of the while loop. Since we reduce the
size of $Z$ by at least 1, there can be at most $k$ iterations of the while
loop. This completes the description of our algorithm.

0.1 Input: An index $j\in I_{4}$, a subset $P_{j}$ of points.

0.2 Initialize a variable update to false

0.3 Initialize an index set $Z:=I_{3}\cup I_{4}$.

0.4 while  _update is false _ do

0.5 Let $x$ be the point in $P\setminus\\{c_{i}:i\notin I_{4}\\}$ which
maximizes $\min(U_{x},|B(x,r_{j})\cap P_{j}|)$. Define $C_{j}:=B(x,r_{j})\cap
P_{j}$.

0.6 Pick a subset $L\subseteq Z$ uniformly at random.

0.7 if  _$L$ is empty _ then

0.8 Call InsertBall($x,j,r_{j},3$).

0.9 If $B(x,r_{j})$ was added to $\mathcal{B}_{3}$, set $C_{j}$ as defined
above in line 5.

0.10 Set update to true.

0.11 else

0.12 if  _there is an index $t\in L$ with $r_{t}>r_{j}$ _ then

0.13

0.14 Let $y$ be the point in $B(x,r_{j}+r_{t})\setminus\\{c_{i}:i\notin
I_{4}\\}$ with the maximum capacity $U_{y}$.

0.15 Call InsertBall($y,t,5r_{t},2$);

0.16 If the index $t$ was added to $I_{2}$, remove it from $I_{3}$ and remove
the corresponding ball from $\mathcal{B}_{3}$.

0.17 Set update to true.

0.18 else

0.19 Perform exactly one of the following steps with equal probability:

0.20 (i) Call InsertBall($x,j,5r_{j},2$). Set update to true.

0.21 (ii) Update $Z=Z\setminus L$ and $P_{j}=P_{j}\setminus B(x,3r_{j}).$

0.22

0.23

Algorithm 5 Procedure UpdateBalls($j,P_{j}$) adds a ball to either
$\mathcal{B}_{2}$ or $\mathcal{B}_{3}$.

###  3.2 Analysis

We now analyse the algorithm. We begin with the following key observation
about the procedure InsertBall:

###### Claim

Suppose the algorithm calls InsertBall with parameters $(p,j,r,u)$, then the
point $p\neq c_{i}$ for any $i\in I_{1}\cup I_{2}\cup I_{3}$.

###### Proof

The claim follows from the fact that whenever we call InsertBall$(p,j,r,u)$,
we make sure $p$ has not been selected as the center of any ball in
$\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\mathcal{B}_{3}$. This can be easily
seen by considering each call to this procedure:

  * •

Line 4 of Algorithm 4: At this point $I_{2},I_{3}$ are empty and we make sure
that the point $x\neq c_{i}$ for any $i\in I_{1}$ (line 4).

  * •

Line 4 of Algorithm 4: we ensure that $x\neq c_{i},i\in[k]\setminus I_{4}$ in
line 4.

  * •

Line 5 or line 5 of Algorithm 5: in line 5, we make sure that $x\neq
c_{i},i\in[k]\setminus I_{4}$.

  * •

Line 5 of Algorithm 5: we ensure in line 5 that $y\neq c_{i},i\in[k]\setminus
I_{4}$.

We now bound the number of iterations in the procedure UpdateBalls.

###### Claim

The while loop in a particular invocation of UpdateBalls has at most $k$
iterations. The procedure InsertBall is called at most $O(k^{2})$ times, and
the number of times it chooses the option (ii) is at max $k$.

###### Proof

First consider the while loop in the UpdateBalls procedure. If a particular
iteration of this loop does not end the procedure, then it must execute line
5. Since the set $L\subseteq Z$ is non-empty, the set $Z$ reduces in size
during this iteration. Since the initial size of $Z$ was at most $k$, there
can be at most $k$ iterations of this while loop.

The number of times InsertBall chooses the option (ii) is at max $k$, because
every time the second option is chosen, the size of $I^{\star}$ increases by
$1$, and we never remove anything from $I^{\star}$. During any consecutive
stretch of option (i) choices, each call to InsertBall, either removes an
element from $I_{4}$ or moves an element from $I_{3}$ to $I_{2}$ (line 5).
Hence, the number of consecutive calls to InsertBall that make the first
choice can be at max $2k$.

We first state the desirable events during an iteration of Algorithm 4:

  * •

${\cal E}_{1}$: For each point $p$ considered in line 4, the index $j$ chosen
in line 4 satisfies the condition that $p\in C^{\star}_{j}$.

  * •

${\cal E}_{2}$: For each index $j$ considered in line 4, the subset $T_{j}$
chosen in line 4 satisfies the property that $T_{j}=\\{h\in I_{1}\cup
I_{2}:B_{h}\cap B_{j}^{\star}\neq\emptyset\\}.$

  * •

${\cal E}_{3}:$ For each iteration of the while loop in Algorithm 5, the
subset $L$ picked in line 5 in Algorithm 5 is equal to the set $\\{i\in
Z:B_{i}^{\star}\cap C_{j}\neq\emptyset\\}$.

  * •

${\cal E}_{4}$: In each iteration of the while loop in Algorithm 5, if we
reach line 5, then the choice (i) is taken iff the ball $B(x,3r_{j})\cap
B_{j}^{\star}$ is non-empty.

  * •

${\cal E}_{5}$: Whenever InsertBall($p,j,r,u$) is called, it chooses option
(ii) in line 3 iff $p$ is same as $c_{u}^{\star}$ for some $u\in I_{2}\cup
I_{3}\cup I_{4}$. Further, the index $h$ selected in this step is equal to
$u$.

###### Claim

If the event ${\cal E}_{1}\cap{\cal E}_{5}$ happens, then for each $j\in
I_{1}$, the ball $B_{j}\in\mathcal{B}_{1}$ contains the optimal ball
$B_{j}^{\star}$. Hence, if ${\cal E}_{1}$ happens, the algorithm does not
output fail in line 4. Further, the probability that all the events ${\cal
E}_{1},{\cal E}_{2},{\cal E}_{3},{\cal E}_{4},{\cal E}_{5}$ happen is at least
$1/2^{O(k^{4})}$.

###### Proof

The proof is similar to that of Lemma 2. Suppose ${\cal E}_{1}\cap{\cal
E}_{5}$ happens. For each index $i\in I^{\star}$, $B(c_{i},r_{i})$ contains
$B_{i}^{\star}=B(c_{i}^{\star},r_{i}^{\star})$ because $c_{i}=c_{i}^{\star}$
for such indices and $r_{i}\geq r_{i}^{\star}$. Now if InsertBall executes
option (ii) in line 3, we simply replace $I_{1}$ by $I^{\star}$ and start from
scratch. The only other case when when we add a ball to $\mathcal{B}_{1}$ is
during the while loop in line 4 in Algorithm 4. Consider such an iteration and
assume that InsertBall executes option (i). Let $x$ be the point chosen in
line 4. Then, $d(x,c_{j}^{\star})\leq d(x,p)+d(p,c_{j}^{\star})=2r_{j}$.
Therefore, $B_{j}:=B(x,3r_{j})$ contains $B_{j}^{\star}$. Therefore, there
will be at most $k$ iterations of the while loop in line 4. Thus, the
algorithm won’t output fail in line 4.

The probability that InsertBall always chooses the option (i) or (ii)
correctly is at least $\frac{1}{2^{O(k^{2})}}$, as the number of calls is
$O(k^{2})$ ( Section 3.2) and the probability of making the correct choice in
a single call is $\frac{1}{2}$. Given this happens, the probability that it
correctly guesses the index $h$ is at least $1/k$ for any call where it
chooses option (ii). Hence, $\Pr[{\cal
E}_{5}]\geq\frac{1}{k^{k}}\frac{1}{2^{O(k^{2})}}=\frac{1}{2^{O(k^{2})}}$. Now,
the probability that the chosen index $j$ in line 4 is correct (i.e., $p\in
C_{j}^{\star}$) in each iteration of this while loop is at least $1/k$. Hence,
$\Pr[{\cal E}_{1}|{\cal E}_{5}]\geq 1/k^{O(k^{2})}$, as each such iteration
leads to a call to InsertBall. Conditioned on ${\cal E}_{1}$, the probability
that the choice of $T_{j}$ in line 4 is correct is at least $1/2^{k}$ (since
there are at most $2^{k}$ possibilities for $T_{j}$). Since every iteration of
the while loop in line 4 leads to a call to InsertBall, we see that $\Pr[{\cal
E}_{2}|{\cal E}_{1},{\cal E}_{5}]\geq\frac{1}{2^{O(k^{3})}}.$

Given events ${\cal E}_{1},{\cal E}_{2}$, whenever we reach line 5, we guess
$L$ correctly with probability at least $\frac{1}{2^{k}}$. There are at most
$O(k^{2})$ calls to UpdateBalls, and there are at most $k$ iterations of the
while loop in Algorithm 5. Hence, $\Pr[{\cal E}_{3}|{\cal E}_{1},{\cal
E}_{2},{\cal E}_{5}]\geq\frac{1}{2^{O(k^{4})}}.$ Also, whenever reach line 5,
we guess the choice (i) or (ii) correctly with probability $1/2$. Hence,
$\Pr[{\cal E}_{4}|{\cal E}_{1},{\cal E}_{2},{\cal E}_{3},{\cal
E}_{5}]\geq\frac{1}{2^{O(k^{3})}}$

Now we write down the invariant conditions satisfied during our algorithm. The
condition Invariant 1 was mentioned earlier, but we restate it here:

  * •

Invariant 1: Let $j,j^{\prime}\in I_{3}$ be two distinct indices. Then
$C_{j}\cap C_{j^{\prime}}=\emptyset$. Further, for any $j\in I_{3}$ and $i\in
I_{3}\cup I_{4},$ $B_{i}^{\star}\cap C_{j}=\emptyset.$

  * •

Invariant 2: For any index $j\in I_{1}$, $B_{j}^{\star}\subseteq B_{j}$, where
$B_{j}$ is the ball corresponding to index $j$ in $\mathcal{B}_{1}$. Further,
the radius of $B_{j}$ is at most $3r_{j}$.

  * •

Invariant 3: For any index $j\in I_{2}$, $B_{j}^{\star}\subseteq B_{j}$, where
$B_{j}$ is the ball corresponding to index $j$ in $\mathcal{B}_{2}$. Further,
the radius of $B_{j}$ is at most $5r_{j}$.

  * •

Invariant 4: For any index $j\in I_{4}$, and any index $i\in I_{2}$,
$r_{j}\leq r_{i}$ .

We now show that these invariant conditions are maintained by the algorithm.
The following result follows from the proof of Section 3.2.

###### Claim

Suppose event ${\cal E}_{1}$ happens. Then Invariant 2 is maintained by the
algorithm.

###### Lemma 5

Suppose events ${\cal E}_{1},\ldots,{\cal E}_{5}$ occur. Then the algorithm
maintains all the four invariant conditions mentioned above.

###### Proof

Assume that the events ${\cal E}_{1},\ldots,{\cal E}_{5}$ occur. Section 3.2
already shows that Invariant 2 is maintained by our algorithm. We now show
that the other three invariant conditions hold by induction on the number of
iterations of the while loop in line 4 in Algorithm 4. Just before executing
this while loop for the first time, the index sets $I_{2},I_{3}$ are empty,
and so the three invariant conditions hold vacuously.

Now consider a particular iteration of this while loop and assume that the
invariant conditions hold at the beginning of this iteration. During this
while loop, we shall call InsertBall procedure exactly once. In this
procedure, if the second option is chosen (i.e., line 3), then we shall insert
a ball $B_{h}$ in $\mathcal{B}_{1}$ and an index $h$ in $I_{1}$ such that
$B_{h}$ contains $B_{h}^{\star}$ (since ${\cal E}_{5}$ occurs). Now it is easy
to check that all the invariants continue to hold. Therefore, we shall assume
that this procedure executes the first option in line 3.

Now, two cases arise depending on whether the condition in line 4 is true.
First assume it is true, i.e., there is an index $h\in T_{j}$ such that
$r_{j}\geq{\mathsf{radius}}(B_{h})$. Let $x$ be the point selected in line 4.
Then

$d(x,c_{j^{\star}})\leq
d(x,c_{h})+d(c_{h},c_{j}^{\star})\leq{\mathsf{radius}}(B_{h})+r_{j}+{\mathsf{radius}}(B_{h})+r_{j}\leq
2\cdot{\mathsf{radius}}(B_{h})+2r_{j},$

where we have used the fact that
$d(c_{h},c_{j}^{\star})\leq{\mathsf{radius}}(B_{h})+r_{j}^{\star}$ because
$B_{h}$ and $B^{\star}_{j}$ intersect. Since
$r_{j}\geq{\mathsf{radius}}(B_{h})$, the above is at most $4r_{j}$. It follows
that $B(x,5r_{j})$ contains $B_{j}^{\star}$. This shows that Invariant 3 is
satisfied. Since $j$ was chosen to have the highest $r_{j}$ value among all
indices in $I_{4}$, Invariant 4 is also satisfied. Finally, we do not change
$I_{3}$ and only remove an index from $I_{4}$. Therefore, Invariant 1
continues to hold.

We now consider the more involved case when the outcome of the if condition in
line 4 is false. In this case, $r_{j}<{\mathsf{radius}}(B_{h})$ for all $h\in
T_{j}$. We first argue that $B_{j}^{\star}\subseteq E_{h}$ for any $h\in
T_{j}$ (where $E_{h}=B(c_{h},9r_{h})$ as defined in line 4). To see this, note
that, $B_{j}^{\star}\subseteq B(c_{h},{\mathsf{radius}}(B_{h})+2r_{j})$, as
$B_{j}^{\star}$ and $B_{h}$ intersect. If $h\in I_{1}$, from Invariant 2,
${\mathsf{radius}}(B_{h})\leq 3r_{h}$, so ${\mathsf{radius}}(B_{h})+2r_{j}\leq
3{\mathsf{radius}}(B_{h})\leq 9r_{h}$. Otherwise,
${\mathsf{radius}}(B_{h})\leq 5r_{h}$ from Invariant 3, and $r_{j}\leq r_{h}$
from Invariant 4. Hence, ${\mathsf{radius}}(B_{h})+2r_{j})\leq
5r_{h}+2r_{h}\leq 9r_{h}$ Thus, $B_{j}^{\star}\subseteq\cap_{h\in
T_{j}}E_{h}$. Since the event ${\cal E}_{2}$ has occurred, we know that
$B_{j}^{\star}\cap B_{h}=\emptyset$ for all $h\in I_{1}\cup I_{2}\setminus
T_{j}$, and the induction hypothesis about Invariant 1 implies that
$B_{j}^{\star}\cap C_{i}=\emptyset$ for all $i\in I_{3}$. Thus, the set
$P_{j}$ defined in line 4 of Algorithm 4 contains $B_{j}^{\star}$.

###### Claim

$B_{j}^{\star}\subseteq P_{j}$ during the execution of the procedure
UpdateBalls($j,P_{j})$. Further, for every index $i\in(I_{3}\cup
I_{4})\setminus Z$, $B_{i}^{\star}\cap P_{j}=\emptyset$.

###### Proof

We show this by induction on the number of iterations of the while loop in the
procedure UpdateBalls($j,P_{j})$. Since $Z$ is initialized to $I_{3}\cup
I_{4}$, and $B_{j}^{\star}\subseteq P_{j}$ when this procedure is called, the
claim is true at the beginning.

Now suppose the claim is true at the beginning of an iteration of this while
loop. Assume that we go through one iteration of the while loop and come back
to line 5. Then we must have executed the case in line 5. Since event ${\cal
E}_{3}\cap{\cal E}_{4}$ happens, we know that $L=\\{i\in Z:B_{i}^{\star}\cap
C_{j}\neq\emptyset\\}$, $r_{t}\leq r_{j}$ for all $t\in L$ and
$B(x,3r_{j})\cap B_{j}^{\star}$ is empty. Therefore, $B_{j}^{\star}\subseteq
P_{j}^{\prime}:=P_{j}\setminus B(x,3r_{j})$. We claim that for any $t\in L$,
$B_{t}^{\star}\cap P_{j}^{\prime}$ is empty. Indeed, we know that
$B_{t}^{\star}$ intersects $C_{j}$ (by event ${\cal E}_{4}$) and $r_{t}\leq
r_{j}$. Since $C_{j}\subseteq B(x,r_{j})$, it follows that
$B_{t}^{\star}\subseteq B(x,3r_{j})$. Therefore, $B_{t}^{\star}$ does not
intersect $P_{j}^{\prime}$. Thus, we see that the desired claim holds at the
end of line 5 as well.

Now we consider the various cases on how this procedure terminates:

  * •

The ball $B(x,r_{j})$ was added in line 5: Since event ${\cal E}_{3}$
occurred, we know that $B_{i}^{\star}\cap C_{j}$ is empty for all $i\in Z$.
Combining this with Section 3.2 and the fact that $C_{j}\subseteq P_{j}$, we
see that $B_{i}^{\star}\cap C_{j}$ is empty for all $i\in I_{3}\cup I_{4}$.
Since $P_{j}$, as defined in line 4, is disjoint from $\cup_{i\in
I_{3}}C_{j}$, we see that adding the index $j$ to $I_{3}$, and $B(x,r_{j})$
along with $C_{j}$ to $\mathcal{B}_{3}$ maintains Invariant 1. Since we do not
change $I_{1},I_{2}$ and $I_{4}$ only reduces, the other three invariants
continue to be satisfied.

  * •

the ball $B_{t}:=B(y,r_{j}+r_{t})$ was added to $\mathcal{B}_{2}$ in line 5
(and the index $t$ and the corresponding ball was removed from
$\mathcal{B}_{3}$): Since we are removing a ball from $\mathcal{B}_{3},$
Invariant 1 continues to be satisfied. No new ball is added to
$\mathcal{B}_{1}$ and hence, Invariant 2 is also satisfied. We check Invariant
3 now: we know that $r_{t}>r_{j}$ and $B_{t}^{\star}$ intersects $B_{j}$
(since ${\cal E}_{3}$ has occurred). Therefore,

$d(y,c_{t}^{\star})\leq
d(y,x)+d(x,c_{t}^{\star})\leq(r_{j}+r_{t})+(r_{j}+r_{t}).$

Since $r_{j}\leq r_{t}$, the above is at most $4r_{t}$. Therefore,
$B(y,5r_{t})$ contains $B_{t}^{\star}$. Thus, Invariant 3 is satisfied. It
remains to check Invariant 4: note that the index $j\in I_{4}$ was chosen
because it has the highest $r_{j}$ value among all the indices in $I_{4}$
(line 4). Since $r_{t}\geq r_{j}$, we see that Invariant 4 is also satisfied.

  * •

The ball $B(x,5r_{j})$ is added to $\mathcal{B}_{2}$ in line 5: Since
$I_{1},I_{3}$ do not change and the set $I_{4}$ shrinks, invariants Invariant
1, Invariant 2 continue to be satisfied. Since ${\cal E}_{4}$ occurs, we know
that $B(x,3r_{j})\cap B_{j}^{\star}$ is non-empty. Hence, $B(x,5r_{j})$
contains $B_{j}^{\star}$ and so, Invariant 3 is satisfied. Finally, Invariant
4 is satisfied because of the manner index $j\in I_{4}$ was chosen (line 4).

This completes the proof of the desired lemma.

We now show that the centers of the balls added by our algorithm have
sufficient capacities:

###### Lemma 6

Assume that the events ${\cal E}_{1},\ldots,{\cal E}_{5}$ occur. For each ball
$B_{j}\in\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\mathcal{B}_{3}$ centered at
$c_{j}$, the capacity of $c_{j}$ is at least $|C_{j}^{\star}|$.

###### Proof

We first observe that the following property is maintained during the
execution of the algorithm:

###### Claim

For any index $i\in I_{4}$, the optimal center $c_{i}^{\star}$ is not the
center of any ball in $\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\mathcal{B}_{3}.$

###### Proof

We add a ball to $\mathcal{B}_{2}\cup\mathcal{B}_{3}$ only during case (i) of
InsertBall. But if $p$ happens to be $c_{i}^{\star}$ for some $i\in I_{2}\cup
I_{3}\cup I_{4}$, then ${\cal E}_{5}$ implies that we invoke case (ii), a
contradiction. Therefore, the claim holds.

When we invoke case (ii) of InsertBall and a ball $B_{j}$ to
$\mathcal{B}_{1}$, Invariant 5 implies that the center of this ball is
$c_{j}^{\star}$ and hence, the Lemma holds trivially. Therefore, for rest of
the proof, consider only the cases when we execute option (i) (i.e., line 3)
when the InsertBall procedure is called. We now go through all such
possibilities:

  * •

We add the ball $B(x,3r_{j})$ to $\mathcal{B}_{1}$ in line 4: we know by the
property shown above that $c_{j}^{\star}$ has not been used as the center of
any selected ball yet. Since $p\in B_{j}^{\star}$ (by event ${\cal E}_{1}$),
$c_{j}^{\star}$ is a candidate for the point $x$ selected in line 4.
Therefore, $U_{x}\geq U_{c_{j}^{\star}}\geq|C_{j}^{\star}|.$

  * •

We insert the ball $B(x,5r_{j})$ in line 4: again, we know that
$c_{j}^{\star}$ has not been used as a center yet. Since $B_{h}\cap
B_{j}^{\star}$ is non-empty (since event ${\cal E}_{2}$ occurs),
$d(c_{h},c_{j}^{\star})\leq{\mathsf{radius}}(B_{h})+r_{j}$. Therefore,
$c_{j}^{\star}$ is one of the candidates for the point $x$. Thus, $U_{x}\geq
U_{c_{j}^{\star}}\geq|C_{j}^{\star}|.$

  * •

We add a ball centered at $x$ in line 5 or line 5 in UpdateBalls procedure: We
know by Section 3.2 that $B_{j}^{\star}\subseteq P_{j}$. Therefore, for
$x=c_{j}^{\star}$, the quantity $\min(U_{x},|B(x,r_{j})\cap P_{j}|)$ is at
least $|C_{j}^{\star}|$. Since $c_{j}^{\star}$ has not been chosen as a center
yet, it follows from line 5 that $U_{x}\geq|C_{j}^{\star}|$.

  * •

We add the index $t$ to $I_{2}$ and a ball centered at $y$ to
$\mathcal{B}_{2}$ in line 5: Since $B_{j}\cap B_{t}^{\star}\neq\emptyset$ (by
event ${\cal E}_{3}$), $d(x,c_{t}^{\star})\leq r_{j}+r_{t}$. We claim that
$c_{t}^{\star}$ has not been used a center of any ball in
$\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\mathcal{B}_{3}$. Indeed, we know that
$t\in I_{3}\cup I_{4}$. If $t\in I_{4}$, Section 3.2 implies that
$c_{t}^{\star}$ has not been used as a center. If $t\in I_{3}$, then Invariant
1 implies that $c_{t}^{\star}$ is not contained in the ball
$B_{t}\in\mathcal{B}_{3},$ and hence, has not been used a center yet. Since
$d(x,c_{t}^{\star})\leq r_{j}+r_{t}$, $c_{t}^{\star}$ is a candidate for the
point $y$ chosen in line 5. Therefore, $C_{y}\geq
C_{c_{t}^{\star}}\geq|C_{t}^{\star}|$.

###### Lemma 7

Suppose events ${\cal E}_{1},\ldots,{\cal E}_{5}$ occur. Let
$\\{B(c_{j},9r_{j}):j\in[k]\\}$ be the set of balls output by Algorithm 4.
Then there is a feasible solution to this instance where each center $c_{j}$
is assigned at most $U_{j}$ points, and if a point $p$ is assigned to a center
$c_{j}$, then $p\in B_{j}$.

###### Proof

For the balls in $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$, Invariant 2 and
Invariant 3 shows that they cover the corresponding optimal balls. However
this is not true for the balls in $\mathcal{B}_{3}$ (in fact Invariant 1 shows
quite the opposite). Thus handling these balls require more nuanced argument.
For each $j\in I_{3}$, we claim that $|C_{j}|\geq|C_{j}^{\star}|$. Indeed, as
the proof of Lemma 6 shows, when we define $C_{j}$ as in line 5,
$c_{j}^{\star}$ is also a candidate for the point $x$ chosen in this step.
Therefore,
$\min(U_{c_{j}},|C_{j}|)\geq\min(U_{c_{j}^{\star}},|C_{j}^{\star}|)$, which
implies that $|C_{j}|\geq|C_{j}^{\star}|$. Therefore, for each $j\in I_{3}$,
let $D_{j}$ be an arbitrary subset of $C_{j}$ with $|D_{j}|=|C_{j}^{\star}|$.
It follows from Invariant 1 that $D_{i}\cap D_{j}=\phi$ for any $i,j\in
I_{3},i\neq j$. For any $j\in I_{3},i\in T_{j}$, define $S_{ji}:=D_{j}\cap
C_{i}^{\star}$. Note that $\cup_{i\in T_{j}}S_{ji}=D_{j}$ because $T_{j}$ is
the set of indices $i$ for which $C_{j}\cap C_{i}^{\star}$ is non-empty. Also,
the sets $S_{ji}$ are disjoint as $C_{i}^{\star}$ are disjoint, and therefore
$\sum_{i\in T_{j}}|S_{ji}|=|D_{j}|=|C_{j}^{\star}|$. Hence, we can partition
the set $C_{j}^{\star}$ as $C_{j}^{\star}=\cup_{i\in T_{j}}V_{ji}$, where
$V_{ji}$’s are mutually disjoint over different $i$ and $|V_{ji}|=|S_{ji}|$.

Now, let us define the clusters $X_{1},X_{2},\ldots X_{k}$ as follows:

  * •

For each $i\in I_{3}$, $X_{i}=D_{i}$

  * •

For each $i\in I_{1}\cup I_{2}$, $X_{i}=(C_{i}^{\star}\setminus\cup_{j:i\in
T_{j}}S_{ji})\cup(\cup_{j:i\in T_{j}}V_{ji})$. Note the following properties:

    * –

$S_{ji}=C_{i}^{\star}\cap D_{j}\subseteq C_{i}^{\star}$

    * –

$V_{ji}\subseteq C_{j}^{\star}$ meaning $V_{ji}\cap C_{i}^{\star}=\phi$

    * –

For for two indices $x,y\in I_{3}$ such that $i\in T_{x}\cap T_{y}$,
$S_{xi}\cap S_{yi}=\phi$, as $D_{x}\cap D_{y}=\phi$ and $V_{xi}\cap
V_{yi}=\phi$, as $C_{x}^{\star}\cap C_{y}^{\star}=\phi$

Hence, $|X_{i}|=|C_{i}^{\star}|-\sum_{j:i\in T_{j}}|S_{ji}|+\sum_{j:i\in
T_{j}}V_{ji}=C_{i}^{\star}$ as $|S_{ji}|=|V_{ji}|$ for $j$ such that $i\in
T_{j}$.

We complete the proof by claiming that $X$ is a valid assignment, that is:

  1. 1.

For each $i\in[k]$, $|X_{i}|\leq U_{c_{i}}$.

  2. 2.

For each $i\in[k]$, $X_{i}\subseteq B(c_{i},9r_{i})$

  3. 3.

$X_{i}\cap X_{j}=\phi$ for any $i\neq j\in[k]$ and $\cup_{i\in[k]}X_{i}=P$.

The first part can be proved by noting that for all $i\in[k]$,
$|X_{i}|=|C_{i}^{\star}|$ and then using Lemma 6.

For the second part, if $i\in I_{3}$, $X_{i}=D_{i}\subseteq C_{i}\subseteq
B_{i}=B(c_{i},r_{i})\subseteq B(c_{i},9r_{i})$. Otherwise, note that
$C_{i}^{\star}\subseteq B_{i}^{\star}\subseteq B(c_{i},5r_{i})\subseteq
B(c_{i},9r_{i})$ holds from Invariant 3. Also, for any $j$ with $i\in T_{j}$,
note that $V_{ji}\subseteq C_{j}^{\star}\subseteq P_{j}\subseteq
B(c_{i},9r_{i})$.

For the third part, consider $i\neq j\in[k]$. There are three cases:

  * •

$i,j\in I_{3}$: In this case, $X_{i}\cap X_{j}=D_{i}\cap D_{j}=\phi$

  * •

$i,j\in I_{1}\cup I_{2}$: In this case, $C_{i}^{\star}\cap
C_{j}^{\star}=\phi$, and for any two indices $x,y$, with $i\in T_{x}$ and
$j\in T_{y}$, $V_{xi}\cap V_{yj}=\phi$ because if $x\neq y$, then
$V_{xi}\subseteq C_{x}^{\star}$ and $V_{yj}\subseteq C_{y}^{\star}$, and
otherwise if $x=y$, $V_{xi}$ and $V_{yj}$ are disjoint sets in a partition of
$C_{x}^{\star}$

  * •

$i\in I_{1}\cup I_{2},j\in I_{3}\cup I_{2}$ or vice versa. Assume wlog that
$i\in I_{1}\cup I_{2},j\in I_{3}$. Here,
$D_{j}\cap(C_{i}^{\star}\setminus\cup_{l:i\in T_{l}}S_{li})=\phi$ because we
remove $S_{ji}=D_{j}\cap C_{i}^{\star}$ from $C_{i}^{\star}$ when forming
$X_{i}$. Also, $D_{i}\cap V_{li}=\phi$ for any $l$ with $i\in T_{l}$, because
$V_{li}\subseteq C_{l}^{\star}$, $D_{j}\subseteq C_{j}$ and $C_{j}\cap
C_{l}^{\star}=\phi$, from Invariant 1.

Now, since the clusters are disjoint and $|X_{i}|=|C_{i}^{\star}|$ for all
$i\in[k]$,
$|\cup_{i\in[k]}X_{i}|=\sum_{i\in[k]}|X_{i}|=\sum_{i\in[k]}|C_{i}^{\star}|=|P|$.
This means that $\cup_{i\in[k]}X_{i}=P$, as $X_{i}\subseteq P$ for all
$i\in[k]$

###### Lemma 8

The total cost of the solution produced by Algorithm 4 is at most
$9\sum_{j\in[k]}r_{j}$. Further, the total $L_{p}$ norm of the radii of the
clusters produced by this algorithm is at most
$9\left(\sum_{j\in[k]}r_{j}^{p}\right)^{1/p}$.

###### Proof

Clearly, the sum of $p^{th}$ powers of the radii of the balls in the
algorithm’s output is:
$\sum_{j\in[k]}(9r_{j})^{p}=9^{p}\sum_{j\in[k]}r_{j}^{p}$.

It follows from Section 3.2, Lemma 7 and Lemma 8 that the algorithm outputs a
$(9+\varepsilon)$ approximate solution with probability at least
$1/2^{O(k^{4})}$. This probability bound can be improved to $1/2^{O(k^{3})}$
through a more fine-grained analysis. For this, note that the invariants $1,3$
and $4$ only need to be satisfied after the last call to InsertBall that
chooses option (ii). This allows us to relax the definitions of ${\cal
E}_{2},{\cal E}_{3},{\cal E}_{5}$, such that $\Pr[{\cal E}_{1}\cap{\cal
E}_{2}\cap{\cal E}_{3}\cap{\cal E}_{4}\cap{\cal E}_{5}]\geq 1/2^{O(k^{3})}$

###  3.3 Improvement in approximation ratio from $9$ to $4+\sqrt{13}$

In this section, we briefly show that with a more careful choice of
parameters, we can improve the approximation ratio from 9 to about 7.606. We
use a parameter $\alpha$ that shall be fixed later. We make the following
changes in Algorithm 4:

  * •

The condition in line 4 becomes
“$r_{j}\geq\alpha\cdot{\mathsf{radius}}(B_{h})$”.

  * •

Line 4 remains unchanged, i.e., $x$ is the maximum capacity point in
$B(c_{h},{\mathsf{radius}}(B_{h})+r_{j})$ (other than $\\{c_{i}:i\notin
I_{4}\\}$). But line 4 changes to “Call
UpdateBalls$(x,j,2\cdot{\mathsf{radius}}(B_{h})+3r_{j},2)$.”

  * •

The definition of the ball $E_{h}$ in line 4 changes. Recall that $h$ belongs
to the set $T_{j}$ here. Now we differentiate between two cases. When $h\in
I_{1}$, then we define $E_{h}$ as $B(c_{h},3(1+2\alpha)r_{h})$. The other case
is when $h\in I_{2}$. In this case, we define $E_{h}$ as
$B(c_{h},(5+\frac{2}{\alpha})r_{h}).$

  * •

In line 4, we now output $\\{B(c_{j},3(1+2\alpha)r_{j}):j\in
I_{1}\\}\cup\\{B(c_{j},(5+\frac{2}{\alpha})r_{j}):j\in
I_{2}\\}\cup\mathcal{B}_{3}$

A routine modification of the analysis in the previous section shows that the
approximation ratio now becomes $\max(3(1+2\alpha),5+\frac{2}{\alpha})$ ,
whose minimum possible value is $4+\sqrt{13}\approx 7.606$ at
$\alpha=\frac{1+\sqrt{13}}{6}$.

##  4 Hardness of Approximation for Capacitated $k$-sumRadii

In this section, we prove Theorem 1.3. This result states that assuming the
Exponential Time Hypothesis (ETH), there exists a constant $c>1$ such that any
$c$-approximation for
Capacitated $k$-sumRadii must have running time exponential in $k$. The proof
of this result relies on reduction from the Vertex Cover problem on constant
degree graphs. We shall use the following result that follows from Dinur’s PCP
Theorem [8]. Some of the details can be found in [1].

###### Theorem 4.1

Assume that ETH holds. Then there exist constants $\varepsilon,d>0$ such that
the following holds: any algorithm for Vertex Cover on graphs with maximum
vertex degree at most $d$ that distinguishes between the case when the input
graph $G$ has a vertex cover of size at most $\frac{2n}{3}$ and the case when
$G$ has a vertex cover of size at least $\frac{2n}{3}\cdot(1+\varepsilon)$,
must have running time $2^{\Omega\left(\frac{n}{\mathsf{polylog}n}\right)}$.

Let $d$ be the constant stated in Theorem 4.1. Consider an instance ${\cal I}$
of Vertex Cover. Let the instance ${\cal I}$ be specified by a graph
$G=(V,E)$, where each vertex has degree at most $d$. We now construct an
instance ${\cal I}^{\prime}$ of Capacitated $k$-sumRadii as follows (see
Figure 1):

Figure 1: Reduction from Vertex Cover to Capacitated $k$-sumRadii: points of
the form $p_{e}$ are colored green, points $p_{v}$ are colored red. The subset
of points $Q_{v}$ associated with each $p_{v}$ are colored yellow and the
special point $p^{\star}$ is colored blue. The edges denote the metric on
these points.

Let $n=|V|$. We define the set of points $P$ in ${\cal I}^{\prime}$. For every
edge $e\in E$, there is a point $p_{e}$ of capacity $0$. For every vertex
$v\in V$, there is a point $p_{v}$ with capacity $2d+1$. Further, for every
point $p_{v}$, we associate a set $Q_{v}$ of $d$ new points, each with
capacity 0. Finally, there is a special point $p^{\star}$ with capacity
$\frac{n(d+1)}{3}+1$.

In order to specify the metric on $P$, we first define an unweighted graph
$H=(P,F)$, where $P$ is the vertex set and $F$ is the set of edges. For each
$p_{v}$, we have an edge $(p_{v},p^{\star})$ We also have edges
$(w,p_{v}),(w,p^{\star})$ for each $w\in Q_{v}$). For each vertex $p_{e}$,
where $e=(u,v)$ is an edge in $E$, we add edges $(p_{e},p_{u})$ and
$(p_{e},p_{v})$ to the edge set $F$. The distance between two nodes in $P$ is
given by the shortest path distance in $H$. Finally, we set the parameter
$k=\frac{2n}{3}+1$. We now show that this reduction has the desired
properties:

###### Lemma 9

If the graph $G$ in the instance ${\cal I}$ has a vertex cover of size at most
$2n/3$, then there is a solution to ${\cal I}^{\prime}$ with objective
function value at most $k$.

###### Proof

Let $V^{\prime}$ be a vertex cover of size exactly $2n/3$ in $G$ (we can add
extra vertices to a vertex cover if its size is less than $2n/3$). Consider a
solution to ${\cal I}^{\prime}$ where we locate a center at each of the points
$p_{v},v\in V^{\prime}$. Further, we locate a center at $p^{\star}$. Clearly,
we have opened at most $k$ centers – let $C$ denote the set of open centers.

We now specify the assignment of points in $P$ to the centers. First consider
a point $p_{e},e=(u,v)$. We know that at least one of $u$ and $v$ belong to
$V^{\prime}$, and hence, either $p_{u}$ or $p_{v}$ (or both) lie in $C$ –
assume wlog that $p_{u}\in C$. Then, we assign $p_{e}$ to $p_{u}$. For every
$v\in V^{\prime},$ we assign $p_{v}$ and all the points in $Q_{v}$ to $p_{v}$.
All the remaining points are assigned to $p^{\star}$.

It is easy to check that each point in $P$ is assigned to a center which is
joined to it by an edge in $H.$ Thus, the radius of each cluster is at most 1,
and so the total cost of this solution is at most $k$. It remains to verify
the capacity constraints. Every center $p_{v}\in C$ is assigned at most $2d+1$
points because $|Q_{v}|=d,$ and the degree of $v$ is at most $d$. For the
center $p^{\star}$, the set of points assigned to it (besides $p^{\star}$
itself) is given by $\bigcup_{v\in V\setminus V^{\prime}}\left(\\{v\\}\cup
Q_{v}\right).$ The size of this set is $(d+1)|V\setminus
V^{\prime}|=(d+1)n/3$. Thus, we satisfy the capacity constraint for
$p^{\star}$ as well. This proves the desired result.

###### Lemma 10

If the graph $G$ in the instance ${\cal I}$ has a minimum vertex cover of size
at least $(2n/3)\cdot(1+\varepsilon)$, then any solution to ${\cal
I}^{\prime}$ has cost at least $k\cdot(1+\frac{\varepsilon}{2d})$.

###### Proof

For sake of brevity, let $P_{V}$ denote the set of points $\\{p_{v}:v\in V\\}$
and $P_{E}$ denote $\\{p_{e}:e\in E\\}$. The only points with non-zero
capacity are those in $P_{V}$ and the special node $p^{\star}$. Therefore,
consider a solution obtained by choosing $p^{\star}$ and a subset $S$ of
$2n/3$ points from $P_{V}$. In the solution obtained above, let
$S_{0}\subseteq S$ by the set of points $p_{v}$ for which the corresponding
cluster centered at $p_{v}$ has radius 0. Define $S_{1},S_{\geq 2}$ similarly.
First observe that at least $2n\varepsilon/3$ points in $P_{E}$ are at a
distance at least 2 from the set $S^{\prime}:=S\cup\\{p^{\star}\\}$. Indeed,
there must be at least $2n\varepsilon/3$ edges which are not covered by $S$
(otherwise there is a vertex cover of size less than $2n(1+\varepsilon)/3$ in
$G$). The points in $P_{E}$ corresponding to these edges must be assigned to a
point in $S_{\geq 2}$ – let $P_{E}^{\prime}$ denote this susbet of $P_{E}$.

###### Claim

$|S_{0}|+\frac{2n\varepsilon}{3d}\leq|S_{\geq 2}|.$

###### Proof

We first observe that

$\displaystyle|S_{0}|\cdot
d+\frac{n(d+1)}{3}+\frac{2n\varepsilon}{3}\leq\frac{n(d+1)}{3}+|S_{\geq
2}|\cdot d$ (1)

The l.h.s. of the above inequality counts the number of points which are
covered by clusters of radius at least 2 or are assigned to $p^{\star}$. The
term $|S_{0}|d$ counts the number of points in $Q_{v}$ for $v\in S_{0}$. The
term $n(d+1)/3$ counts the points in $\\{v\\}\cup Q_{v}$ for all $v\in
P_{V}\setminus S$. And the term $\frac{2n\varepsilon}{3}$ accounts for the set
of points in $P_{E}^{\prime}$.

Now consider the r.h.s. First it is not hard to see that for any point $v\in
S_{\geq 2}$, the points in $Q_{v}$ should be assigned to $v$. This leaves a
capacity of only $d$ for other points which can be assigned to such a point
$v.$ Thus the r.h.s. above accounts for the total number of points (other than
$Q_{v},v\in S_{\geq 2}$) that can be assigned to $p^{\star}$ or $S_{\geq 2}$.
The desired result now follows directly from (1).

The cost of the solution $S\cup\\{p^{\star}\\}$ is at least
$1+|S_{1}|+2\cdot|S_{\geq 2}|$. Now, since
$|S_{0}|+\frac{2n\varepsilon}{3d}\leq|S_{\geq 2}|$, we see that this cost is
at least

$1+|S_{1}|+|S_{0}|+\frac{2n\varepsilon}{3d}+|S_{\geq
2}|=1+\frac{2n}{3}+\frac{2n\varepsilon}{3d}=k\cdot\left(1+\frac{\varepsilon}{2d}\right).$

Theorem 1.3 now follows from Theorem 4.1, Lemma 9 and Lemma 10.

## References

  * [1] Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar.  Approximate Clustering with Same-Cluster Queries.  In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1–40:21, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2018/8335, doi:10.4230/LIPIcs.ITCS.2018.40.
  * [2] Sayan Bandyapadhyay, William Lochet, and Saket Saurabh.  FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii.  In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volume 258 of LIPIcs, pages 12:1–12:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi:10.4230/LIPIcs.SoCG.2023.12.
  * [3] Sayan Bandyapadhyay and Kasturi Varadarajan.  Approximate Clustering via Metric Partitioning.  In Seok-Hee Hong, editor, 27th International Symposium on Algorithms and Computation (ISAAC 2016), volume 64 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2016/6775, doi:10.4230/LIPIcs.ISAAC.2016.15.
  * [4] B. Behsaz and M.R. Salavatipour.  On minimum sum of radii and diameters clustering.  Algorithmica, 73:143–165, 2015.  URL: https://doi.org/10.1007/s00453-014-9907-3.
  * [5] Mihai Bădoiu, Sariel Har-Peled, and Piotr Indyk.  Approximate clustering via core-sets.  In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC ’02, page 250–257, New York, NY, USA, 2002. Association for Computing Machinery.  doi:10.1145/509907.509947.
  * [6] Moses Charikar and Rina Panigrahy.  Clustering to minimize the sum of cluster diameters.  J. Comput. Syst. Sci., 68(2):417–441, 2004.  doi:10.1016/j.jcss.2003.07.014.
  * [7] C.L.Monma and S.Suri.  Partitioning points and graphs to minimize the maximum or the sum of diameters.  Graph Theory, Combinatorics and Applications, pages 880-912, 1991.
  * [8] Irit Dinur.  The pcp theorem by gap amplification.  J. ACM, 54(3):12–es, jun 2007.  doi:10.1145/1236457.1236459.
  * [9] Srinivas Doddi, Madhav V. Marathe, S. S. Ravi, David Scot Taylor, and Peter Widmayer.  Approximation algorithms for clustering to minimize the sum of diameters.  Nord. J. Comput., 7(3):185–203, 2000.
  * [10] Zachary Friggstad and Mahya Jamshidian.  Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters.  In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms (ESA 2022), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 56:1–56:14, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2022/16994, doi:10.4230/LIPIcs.ESA.2022.56.
  * [11] Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi Varadarajan.  On metric clustering to minimize the sum of radii.  Algorithmica, 57:484–498, 2010.  URL: https://doi.org/10.1007/s00453-009-9282-7.
  * [12] Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi Varadarajan.  On clustering to minimize the sum of radii.  SIAM Journal on Computing, 41(1):47–60, 2012.  arXiv:https://doi.org/10.1137/100798144, doi:10.1137/100798144.
  * [13] Pierre Hansen and Brigitte Jaumard.  Cluster analysis and mathematical programming.  Math. Program., 79:191–215, 1997.  doi:10.1007/BF02614317.
  * [14] M. Henzinger, D. Leniowski, and C. Mathieu.  Dynamic clustering to minimize the sum of radii.  Algorithmica, 82:3183–3194, 2020.  URL: https://doi.org/10.1007/s00453-020-00721-7.
  * [15] Tanmay Inamdar and Kasturi R. Varadarajan.  Capacitated sum-of-radii clustering: An FPT approximation.  In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 62:1–62:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.ESA.2020.62.