CNRS & Sorbonne Université Carnegie Mellon UniversitySupported in part by NSF
awards CCF-1536002, CCF-1540541, and CCF-1617790. Vincent Cohen-Addad and
Jason Li [500]Theory of computation Facility location and clustering
[500]Theory of computation Fixed parameter tractability [300]Mathematics of
computing Probabilistic algorithms [100]Mathematics of computing
Dimensionality reduction John Q. Open and Joan R. Access 2 42nd Conference on
Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016
Little Whinging, United Kingdom 42 23

# On the Fixed-Parameter Tractability of Capacitated Clustering

Vincent Cohen-Addad  Jason Li

###### Abstract

We study the complexity of the classic capacitated $k$-median and $k$-means
problems parameterized by the number of centers, $k$. These problems are
notoriously difficult since the best known approximation bound for high
dimensional Euclidean space and general metric space is $\Theta(\log k)$ and
it remains a major open problem whether a constant factor exists.

We show that there exists a $(3+\epsilon)$-approximation algorithm for the
capacitated $k$-median and a $(9+\epsilon)$-approximation algorithm for the
capacitated $k$-means problem in general metric spaces whose running times are
$f(\epsilon,k)n^{O(1)}$. For Euclidean inputs of arbitrary dimension, we give
a $(1+\epsilon)$-approximation algorithm for both problems with a similar
running time. This is a significant improvement over the
$(7+\epsilon)$-approximation of Adamczyk et al. for $k$-median in general
metric spaces and the $(69+\epsilon)$-approximation of Xu et al. for Euclidean
$k$-means.

###### keywords:

approximation algorithms, fixed-parameter tractability, capacitated, k-median,
k-means, clustering, core-sets, Euclidean

##  1 Introduction

Clustering under capacity constraints is a fundamental problem whose
complexity is still poorly understood. The capacitated $k$-median and
$k$-means problems have attracted a lot of attention over the recent years
(e.g.: [4, 22, 23, 24, 13, 3, 8, 6]), but the best known approximation
algorithm for capacitated $k$-median remains a somewhat folklore $O(\log
k)$-approximation using the classic technique of embeddings the metric space
into trees that follows from the work of Charikar et al [5] on the
uncapacitated version, see also [1] for a complete exposition.

Arguably, the hardness of the problem comes from having both a hard constraint
on the number of clusters, $k$, and on the number of clients that can be
assigned to each cluster. Indeed, constant factor approximation algorithms are
known if the capacities [22, 23] or the number of clusters can be violated by
a $(1+\epsilon)$ factor [4, 13], for constant $\epsilon$. Moreover, the
capacitated facility location problem admits constant factor approximation
algorithms with no capacity violation. On the other hand and perhaps
surprisingly, the best known lower bound for capacitated $k$-median is not
higher than the $1+2/e$ lower bound for the uncapacitated version of the
problem.

Thus, to improve the understanding of the problem a natural direction consists
in obtaining better approximation algorithms in some specific metric spaces,
or through the fixed-parameter complexity of the problem. For example, a
quasi-polynomial time approximation scheme (QPTAS) for capacitated $k$-median
in Euclidean space of fixed dimension with $(1+\epsilon)$ capacity violation
was known since the late 90’s [2]. This has been recently improved to a PTAS
for $\mathbb{R}^{2}$ and a QPTAS for doubling metrics without capacity
violation [9]. It remains an interesting open question to obtain constant
factor approximation for other metrics such as planar graphs or Euclidean
space of arbitrary dimension.

For many optimization problems are at least W[1]-hard and so obtaining exact
fixed-parameter tractable (FPT) algorithms is unlikely. However, FPT
algorithms have recently shown that they can help break long-standing barriers
in the world of approximation algorithms. FPT approximation algorithms
achieving better approximation guarantees than the best known polynomial-time
approximation algorithms for some classic W[1]- and W[2]-hard problems have
been designed. For example, for $k$-cut [15], for $k$-vertex separator [21] or
$k$-treewidth-deletion [16].

For the fixed-parameter tractability of the $k$-median and $k$-means problems,
a natural parameter is the number of clusters $k$. The FPT complexity of the
classic uncapacitated $k$-median problem, parameterized by $k$, has received a
lot of attention over the last 15 years. From a lower bound perspective, the
problem is known to be W[2]-hard in general metric spaces and assuming the
exponential time hypothesis (ETH), even for points in $\mathbb{R}^{4}$, there
is no exact algorithm running in time $n^{o(k)}$ [10]. For $\mathbb{R}^{2}$
there exists an exact $n^{O(\sqrt{k})}$ which is the best one can hope for
assuming ETH [10], see also [26].

From an upper bound perspective, _coreset_ constructions and PTAS with running
time $f(k,\epsilon)n^{O(1)}$ have been known since the early 00’s [12, 19, 17,
18, 14]. In the language of fixed-parameter tractability, a coreset is
essentially an “approximate kernel” for the problem: given a set $P$ of $n$
points in a metric space, a coreset is, loosely speaking, a mapping from the
points in $P$ to a set of points $Q$ of size $(k\log n\epsilon^{-1})^{O(1)}$
such that any clustering of $Q$ of cost $\gamma$ can be converted into a
clustering of $P$ of cost at most
$\gamma\pm\epsilon\textup{{cost}}(\text{OPT})$, through the inverse of the
mapping (where OPT is the optimal solution for $P$). See Definition 1.9 for a
more complete definition.

In Euclidean space, several coreset constructions for uncapacitated $k$-median
are independent of the input size and of the dimension and so are truly
approximate kernels. Thus approximation schemes can simply be obtained by
enumerating all possible partitions of the coreset points into $k$ parts,
evaluating the cost of each of them and outputing the one of minimum cost.
However, obtaining similar results in general metric spaces seems much harder
and is likely impossible. In fact, obtaining an FPT approximation algorithm
with approximation guarantee less than $1+2/e$ is impossible assuming Gap-ETH,
see [11].

For the capacitated $k$-median and $k$-means problems much less is known.
First, the coreset constructions or the classic FPT-approximation schemes
techniques of [20, 12] do not immediately apply. Thus, very little was known
until the recent result of Adamczyk et al. [1] who proposed a
$(7+\epsilon)$-approximation algorithm running in time $k^{O(k)}n^{O(1)}$.
More recently, a $(69+\epsilon)$-approximation algorithm for the capacitated
$k$-means problem with similar running time has been proposed by Xu et al.
[28].

###  1.1 Our Results

We present a coreset construction for the capacitated $k$-median and $k$-means
problems, with general capacities, and in general metric spaces (Theorem 2.1).
For an $n$ points set, the coreset has size $\textup{poly}(k\epsilon^{-1}\log
n)$.

From this we derive a $(3+\epsilon)$-approximation for the $k$-median problem
and a $(9+\epsilon)$-approximation for the $k$-means problem in general metric
spaces.

######  Theorem 1.1.

For any $\epsilon>0$, there exists a $(3+\epsilon)$-approximation algorithm
for the capacitated $k$-median problem and a $(9+\epsilon)$-approximation
algorithm for the capacitated $k$-means problem running in time
$(k\epsilon^{-1}\log n)^{O(k)}n^{O(1)}$. This running time can also be bounded
by $(k/\epsilon)^{O(k)}n^{O(1)}$.

This results in a significant improvement over the recent results of Adamczyk
et al. [1] for $k$-median and Xu et al. [28] for (Euclidean) $k$-means, in the
same asymptotic running time.

Moreover, combining with the techniques of Kumar et al. [20], we obtain a
$(1+\epsilon)$-approximation algorithm for points in $\mathbb{R}^{d}$, where
$d$ is arbitrary. We believe that this is an interesting result: while it
seems unlikely that one can obtain an FPT-approximation better than $1+2/e$ in
general metrics, it is possible to obtain an FPT-$(1+\epsilon)$-approximation
in Euclidean metrics of arbitrary dimension. This works for both the
_discrete_ and _continuous_ settings: in the former, the set of centers must
be chosen from a discrete set of candidate centers in $\mathbb{R}^{d}$ and the
capacities may not be uniform, while in the latter the centers can be placed
anywhere in $\mathbb{R}^{d}$ and the capacities are uniform.

######  Theorem 1.2.

For any $\epsilon>0$, there exists a $(1+\epsilon)$-approximation algorithm
for the discrete, Euclidean, capacitated $k$-means and $k$-median problems
which runs in time $(k\epsilon^{-1}\log n)^{k\epsilon^{-O(1)}}$ $n^{O(1)}$.
This running time can also be bounded by
$(k\epsilon^{-1})^{k\epsilon^{-O(1)}}$ $n^{O(1)}$.

######  Theorem 1.3.

For any $\epsilon>0$, there exists a $(1+\epsilon)$-approximation algorithm
for the continuous, Euclidean, capacitated $k$-means and $k$-median problems
running in time $(k\epsilon^{-1}\log n)^{k\epsilon^{-O(1)}}$ $n^{O(1)}$. This
running time can also be bounded by
$(k\epsilon^{-1})^{k\epsilon^{-O(1)}}n^{O(1)}$.

These two results are a major improvement over the 69-approximation algorithm
of Xu et al. [28].

###  1.2 Preliminaries

We now provide a more formal definition of the problems.

######  Definition 1.4.

Given a set of points $V$ in a metric space with distance function $d$,
together with a set of _clients_ $C\subseteq V$, a set of _centers_
$\mathbb{F}\subseteq V$ with a _capacity_ $\eta_{f}\in\mathbb{Z}_{+}$ for each
$f\in\mathbb{F}$, and an integer $k$, the _capacitated $k$-median problem_
asks for a set $F\subseteq\mathbb{F}$ of $k$ _centers_ and an assignment
$\mu:C\mapsto F$ such that $\forall f\in F$,
$|\\{c\mid\mu(c)=f\\}|\leq\eta_{f}$ and that minimizes $\sum_{c\in
C}d(c,\mu(c))$. We abbreviate the capacitated $k$-median instance as
$((V,d),C,\mathbb{F},k)$.

######  Definition 1.5.

The _capacitated $k$-means problem_ is identical, except we seek to minimize
$\sum_{c\in C}d(c,\mu(c))^{2}$.

In the literature, centers are sometimes called _facilities_ , but we will use
_centers_ throughout for consistency.

In the case of the capacitated Euclidean $k$-median and $k$-means, our
approach works for the two main definitions. First, the definition of [28,
20]: $P=\mathbb{R}^{d}$ and capacities are uniform, namely
$\eta_{f}=\eta_{f^{\prime}}$, $\forall f,f^{\prime}\in\mathbb{R}^{d}$. Second,
$P$ is some specific set of points in $\mathbb{R}^{d}$, and for each $f\in P$,
the input specifies a specific capacity $\eta_{f}$

######  Definition 1.6.

Given a capacitated $k$-median instance $((V,d),C,\mathbb{F},k)$ and a set of
chosen centers $F\subseteq\mathbb{F}$, define $\textup{{CapKMed}}(C,F)$ as the
cost of the optimal assignment of the clients to the chosen centers. If it is
impossible, i.e., the sum of the capacities of the centers is less than $|C|$,
then $\textup{{CapKMed}}(C,F)=\infty$.

In our analysis, we will also encounter formulations where the clients have
positive _real_ weights. In this case, we define a _fractional_ variant of
capacitated $k$-median, where the assignment $\mu$ is allowed to be
fractional.

######  Definition 1.7.

Suppose the clients also have weights, so we are given clients $C$ and a
weight function $w:C\to\mathbb{R}_{+}$. Let $W\subseteq C\times\mathbb{R}_{+}$
be the set of pairs $\\{(c,w(c)):c\in C\\}$. Then,
$\textup{{FracCapKMed}}(W,F)$ is the minimum value of $\sum_{c\in C,f\in
F}\mu(c,f)\,d(c,f)$ over all “fractional assignments” $\mu:C\times
F\to\mathbb{R}_{+}$ such that:

  1. 1.

$\forall c\in C$, $\sum_{f\in F}\mu(c,f)=w(c)$, i.e., $\mu$ is a proper
assignment of clients, and

  2. 2.

$\forall f\in F$, $\sum_{c\in C}\mu(c,f)\leq\eta_{f}$, i.e., $\mu$ satisfies
capacity constraints at all centers.

######  Definition 1.8.

We define $\textup{{CapKMeans}}(C,F)$ and $\textup{{FracCapKMeans}}(W,F)$
similarly, except our objective functions are $\sum_{c\in C}d(c,\mu(c))^{2}$
and $\sum_{c\in C,f\in F}\mu(c,f)\,d(c,f)^{2}$, respectively.

It is well-known that, given a set $F\subseteq\mathbb{F}$ of centers, the
problem of finding the optimum $\mu$ is an (integral) _minimum-cost flow_
problem, which can be solved in polynomial time. Therefore, we assume that
every time we have a set $F\subseteq\mathbb{F}$, we can evaluate
$\textup{{CapKMed}}(C,F)$ and $\textup{{CapKMeans}}(C,F)$ in polynomial time.
Similarly, FracCapKMed and FracCapKMeans can be solved through fractional min-
cost flow, or even an LP, in polynomial time. Furthermore, if $W$ is exactly
the set $C$ of clients with weight $1$, i.e., $W=\\{(c,1):c\in C\\}$, then
$\textup{{CapKMed}}(C,F)=\textup{{FracCapKMed}}(W,F)$, since the min-cost flow
formulation of FracCapKMed has integral capacities and therefore integral
flows as well.

We now formally state our definition of coresets, sometimes called _strong_
coresets in the literature.

######  Definition 1.9.

A (strong) coreset for a capacitated $k$-median instance
$((V,d),C,\mathbb{F},k)$ is a set of weighted clients $W\subseteq
C\times\mathbb{R}_{+}$ such that for every set of centers
$F\subseteq\mathbb{F}$ of size $k$,

$\textup{{FracCapKMed}}(W,F)\in(1-\epsilon,1+\epsilon)\cdot\textup{{CapKMed}}(C,F).$

The definition is identical for capacitated $k$-means, except CapKMed and
FracCapKMed are replaced by CapKMeans and FracCapKMeans above.

######  Fact 1.

Let $W$ be a coreset for a capacitated $k$-median instance
$((V,d),C,\mathbb{F},k)$. We have

$\min_{\begin{subarray}{c}F\subseteq\mathbb{F}\\\
|F|=k\end{subarray}}\textup{{FracCapKMed}}(W,F)\in(1-\epsilon,1+\epsilon)\cdot\min_{\begin{subarray}{c}F\subseteq\mathbb{F}\\\
|F|=k\end{subarray}}\textup{{CapKMed}}(C,F),$

In particular, an $\alpha$-approximation of
$\min_{F\subseteq\mathbb{F},|F|=k}\textup{{FracCapKMed}}(W,F)$ implies a
$(1+O(\epsilon))\alpha$-approximation to the capacitated $k$-median instance.
The same holds in the capacitated $k$-means case, with FracCapKMed and CapKMed
replaced by FracCapKMeans and CapKMeans, respectively.

For a capacitated $k$-median or $k$-means instance $((V,d),C,\mathbb{F},k)$,
the _aspect ratio_ is the ratio of the maximum and minimum distances between
any two points in $C\cup F$. It is well-known that we may assume, with a
multiplicative error of $(1+o(1))$ in the optimal solution, that the instance
has $\textup{poly}(n)$ aspect ratio.111For example, the following modification
to the distances $d$ does the trick. First, compute an $O(\log
k)$-approximation [5] to the problem, and let that value be $M$. For any two
points $u,v\in C\cup F$ with $d(u,v)>Mn^{10}$, truncate their distance to
exactly $Mn^{10}$. Then, add $Mn^{-10}$ distance to each pair of points
$u,v\in C\cup F$. The aspect ratio is now bounded by $O(n^{20})$. Therefore,
we will make this assumption throughout the paper.

Lastly, we define $\mathbb{R}_{+}$ and $\mathbb{Z}_{+}$ as the set of positive
reals and positive integers, respectively. As usual, we define _with high
probability (w.h.p.)_ as with probability $1-n^{-Z}$ for an arbitrarily large
positive constant $Z$, fixed beforehand.

##  2 Coreset for $k$-median

In this section, we prove our main technical result for the $k$-median case:
constructing a coreset for capacitated $k$-median of size $\textup{poly}(k\log
n\,\epsilon^{-1})$.

######  Theorem 2.1.

For any small enough constant $\epsilon\geq 0$, there exists a Monte Carlo
algorithm that, given an instance $((V,d),C,\mathbb{F},k)$ of capacitated
$k$-median, outputs a (strong) coreset $W\subseteq C$ with size
$O(k^{2}\log^{2}n/\epsilon^{3})$ in polynomial time, w.h.p.

######  Theorem 2.2.

For any small enough constant $\epsilon\geq 0$, there exists a Monte Carlo
algorithm that, given an instance $((V,d),C,\mathbb{F},k)$ of capacitated
$k$-means, outputs a (strong) coreset $W\subseteq C$ with size
$O(k^{5}\log^{5}n/\epsilon^{3})$ in polynomial time, w.h.p.

Our inspiration for the coreset construction is Chen’s algorithm [7] based on
random sampling. Our algorithm is essentially the same, with slightly worse
bounds in the sampling step, although our analysis is a lot more involved. We
describe the full algorithm in pseudocode below (see Algorithm 1).

At a high level, the algorithm first partitions the client set $C$ into
$\textup{poly}(k,\log n)$ many subsets, called _rings_ , with the help of a
polynomial-time approximate solution (see line 1). The sets are called rings
because they are of the form
$C_{i}\cap\left(\textup{{ball}}(f^{\prime}_{i},R)\setminus\textup{{ball}}(f^{\prime}_{i},R/2)\right)$
for some subset of clients $C_{i}\subseteq C$, some facility
$f^{\prime}_{i}\in\mathbb{F}$, and some positive number $R$ (see line 7).
Then, for each ring $C_{i,R}$, if $|C_{i,R}|$ is small enough, the algorithm
adds the entire ring into the coreset (each with weight $1$); otherwise, the
algorithm takes a random sample of $r=\textup{poly}(k,\log n)$ many clients in
$C_{i,R}$, weights each sampled client by $|C_{i,R}|/r$, and adds the weighted
sample to the coreset. The weighting ensures that the total weight of the
sampled points is always equal to $|C_{i,R}|$. To prove that the algorithm
produces a coreset w.h.p., Chen union bounds over all
$\binom{|\mathbb{F}|}{k}$ choices of a set of $k$ facilities, and shows that
for each choice $F\subseteq\mathbb{F}$, with probability at least
$1-n^{-\Omega(k)}$, the total cost to assign the coreset points to $F$ is
approximately the total cost to assign the original clients $C$ to $F$; this
statement is proved through standard concentration bounds. More details and
intuition for the algorithm can be found in Section 3 of Chen’s paper [7].

Algorithm 1 CoreSet$(I)$

1:$F^{\prime}=\\{f^{\prime}_{1},\ldots,f^{\prime}_{O(k)}\\}\leftarrow$ an
$(O(1),O(1))$ bicriteria solution to instance $I$, namely a capacitated
$O(k)$-median solution with total cost $ALG^{\prime}\leq O(OPT)$
$\triangleright$ using, e.g., [23]

2:$W\leftarrow\emptyset$ $\triangleright$ $W\subseteq C\times\mathbb{R}_{+}$
is the final coreset at the end of the algorithm

3:Define $d_{\min}$ and $d_{\max}$ as the minimum and maximum distances,
respectively, between any two points in $C\cup\mathbb{F}$ $\triangleright$
$d_{\max}/d_{\min}$ is the aspect ratio

4:for each center $f^{\prime}_{i}$ do $\triangleright$ $O(k)$ centers

5: $C_{i}\leftarrow$ the clients in $C$ assigned to center $f^{\prime}_{i}$

6: for each $R$, a power of $2$ in the range $[d_{\min},\,2d_{\max}]$ do
$\triangleright$ $O(\log n)$ iterations, assuming $\textup{poly}(n)$ aspect
ratio

7: $C_{i,R}\leftarrow
C_{i}\cap\left(\textup{{ball}}(f^{\prime}_{i},R)\setminus\textup{{ball}}(f^{\prime}_{i},R/2)\right)$
$\triangleright$ We call the sets $C_{i,R}$ _rings_ , with _ring center_
$f^{\prime}_{i}$. The rings $C_{i,R}$ over all $i,R$ partition the client set
$C$.

8: $r\leftarrow\gamma k\log n/\epsilon^{3}$ for sufficiently large (absolute)
constant $\gamma$

9: if $|C_{i,R}|\leq r$ then

10: add $(c,1)$ to $W$ for each $c\in C_{i,R}$ $\triangleright$ $C_{i,R}$
small enough: add everything into coreset

11: else

12: sample $r$ random centers in $C_{i,R}$ (without replacement)

13: add $(c,\frac{|C_{i,R}|}{r})$ to $W$ for each sampled center $c$
$\triangleright$ weighted so that total weight is still $|C_{i,R}|$

###  2.1 Single ring case

We first restrict ourselves to sampling from a _single_ ring $C_{i,R}\subseteq
C$. That is, while we still consider the cost of serving the clients outside
of $C_{i,R}$, we only perform the sampling (lines 12–13) on one ring
$C_{i,R}$. The general case of $O(k\log n)$ many rings is more complicated
than simply treating each ring separately. Due to space constraints, we only
consider the single ring case in this extended abstract, and the rest is
deferred to the full version.

Fix an arbitrary ring $C_{i,R}$ throughout this section, and define
$C^{\prime}:=C_{i,R}$ for convenience. Let $N:=|C^{\prime}|$ be the number of
clients, and let $f^{\prime}:=f^{\prime}_{i}$ be the ring center of
$C^{\prime}$ (line 4). Let $W^{\prime}$ be the (weighted) centers in $C_{i,R}$
sampled by the algorithm (lines 12–13), together with the (unweighted) centers
in $C\setminus C^{\prime}$, which have weight $1$. Our goal is to show that
$\textup{{FracCapKMed}}(W^{\prime},F)$, the cost after sampling only from
$C^{\prime}$, is close to the original cost $\textup{{CapKMed}}(C,F)$.

######  Lemma 2.3.

W.h.p., for any set of $k$ centers $F\subseteq\mathbb{F}$ satisfying
$\textup{{CapKMed}}(C,F)<\infty$,

$\displaystyle|\textup{{FracCapKMed}}(W^{\prime},F)-\textup{{CapKMed}}(C,F)|\leq\epsilon
NR.$ (1)

It is clear that the output $W$ has size $O(k^{2}\log^{2}n/\epsilon^{3})$. The
rest of this section focuses on proving that $W$ is indeed a coreset, w.h.p.

The intuition behind the $\epsilon NR$ additive error is that we can “charge”
this error to the cost of the bicriteria solution (line 1) that $C^{\prime}$
is responsible for. In particular, the total cost of assigning clients in
$C^{\prime}$ to ring center $f^{\prime}$ in the bicriteria solution is at
least $N\cdot R/2$, since all clients in $C^{\prime}$ are distance at least
$R/2$ to $f^{\prime}$. Therefore, we charge an additive error of $\epsilon NR$
to a $NR/2$ portion of $ALG^{\prime}$, which is a “rate” of $2\epsilon$ to
$1$. If we can do the same for all rings, then since the portions of
$ALG^{\prime}$ sum to $ALG^{\prime}$, our total additive error is at most
$2\epsilon\cdot ALG^{\prime}=O(\epsilon)\cdot OPT$. Finally, replacing
$\epsilon$ with a small enough $\Theta(\epsilon)$ gives the desired additive
error of $\epsilon\cdot OPT$; note that this is where we use that the
approximation ratio of $ALG^{\prime}$ is $O(1)$, and that the specific
approximation ratio is not important (as long as it is constant). The
formalization of this intuition is deferred to the full version; the argument
is identical to Chen’s [7], so we claim no novelty here.

We now prove Lemma 2.3. First of all, if $N=|C^{\prime}|\leq r$ (line 9), then
sampling changes nothing, and
$\textup{{FracCapKMed}}(W^{\prime},F)=\textup{{CapKMed}}(C,F)$. Therefore, for
the rest of the proof, we assume that $N>r=\gamma k\log n/\epsilon^{3}$, with
the $\gamma$ taken to be a large enough constant.

Our high-level strategy is the same as Chen’s: we union bound over all sets of
centers $F\subseteq\mathbb{F}$ of size $k$, and prove that for a fixed set
$F$, the probability of violating (1) is at most $n^{-(k+10)}$.222For
simplicity of presentation, we will focus on a success probability of
$1-n^{-10}$. The constants can be easily tweaked so that the algorithm
succeeds w.h.p., i.e., with probaility $1-n^{-Z}$ for any positive constant
$Z$. Union bounding over all $\leq\binom{n}{k}$ choices of $F$ gives
probability $\leq n^{-10}$ of violating (1), proving the lemma. Therefore,
from now on, we focus on a single, arbitrary set $F\subseteq\mathbb{F}$ of
size $k$ satisfying $\textup{{CapKMed}}(C,F)<\infty$, and aim to show that (1)
fails with probability $\leq n^{-(k+10)}$.

For our analysis, we define a function
$g:\mathbb{R}^{C^{\prime}}_{+}\to\mathbb{R}_{+}$ as follows. For an input
vector $\mathbf{d}\in\mathbb{R}_{+}^{C^{\prime}}$ (indexed by clients in
$C^{\prime}$), consider a min-cost flow instance
$\textup{{FlowInstance}}(\mathbf{d})$ on the graph metric with the following
demands: set demand $d_{c}$ at each client $c\in C^{\prime}$, demand $1$ at
each client $c\in C\setminus C^{\prime}$, and demand $N-\sum_{c\in
C^{\prime}}d_{c}$ (this demand can be negative) at ring center
$f^{\prime}=f^{\prime}_{i}$ (so we are effectively treating $f^{\prime}$ as a
special client with possibly negative demand, not a facility). Observe that
$\textup{{FlowInstance}}(\mathbf{d})$ is a feasible min-cost flow instance,
because the sum of demands is exactly

$\sum_{c\in C^{\prime}}d_{c}+|C\setminus C^{\prime}|+\left(N-\sum_{c\in
C^{\prime}}d_{c}\right)=|C\setminus C^{\prime}|+N=|C|,$

which is the same as the sum of demands in the instance
$\textup{{CapKMed}}(C,F)$, which is feasible by assumption.

Given this setup for an input vector
$\mathbf{d}\in\mathbb{R}^{C^{\prime}}_{+}$, we define the function
$g(\mathbf{d})$ as the min-cost flow of $\textup{{FlowInstance}}(\mathbf{d})$.
Observe that $g(\mathbbm{1})$ is exactly $\textup{{CapKMed}}(C,F)$.

Now define a random vector $X\in\mathbb{R}_{+}^{C^{\prime}}$ as follows. Each
coordinate of $X$ is independently $N/r$ with probability $r/N$ and $0$
otherwise, so that $\mathbb{E}[X]=\mathbbm{1}$. Note that $X$ does not
accurately represent our sampling of $r$ clients, since this process is not
guaranteed to sample exactly $r$ clients. Nevertheless, it is intuitively
clear that with probability $\Omega(1/n)$, $X$ will indeed have exactly $r$
nonzero entries, since $r$ is the expected number; we prove this formally in
the following simple claim (with $p=r/N$), whose routine proof is deferred to
the full version. And if we _condition_ on this event, then $g(X)$ and
$\textup{{CapKMed}}(C,F)$ are now identically distributed.

######  Claim 2.

Let $N$ be a positive integer, and let $p\in(0,1)$ such that $pN$ is an
integer. The probability that $\textup{{Binomial}}(N,p)=pN$ is at least
$\Omega(1/\sqrt{N})$.

In light of all this, our main argument has two steps. First, we show that
$g(X)$ is concentrated around $\mathbb{E}[g(X)]$ using martingales. However,
what we really need is concentration around
$g(\mathbb{E}[X])=g(\mathbbm{1})=\textup{{CapKMed}}(C,F)$, so our second step
is to show that $\mathbb{E}[g(X)]\approx g(\mathbb{E}[X])$ (with probability
$1$). We formally state the lemmas below which, as discussed, together imply
Lemma 2.3.

######  Lemma 2.4.

Assume that $|C^{\prime}|>\Theta(k\log n/\epsilon^{3})$. With probability
$\geq 1-n^{-(k+20)}$, we have $|g(X)-\mathbb{E}[g(X)]|\leq\epsilon NR/2$.

######  Lemma 2.5.

Assume that $|C^{\prime}|>\Theta(k\log n/\epsilon^{3})$. Then,
$|\mathbb{E}[g(X)]-g(\mathbb{E}[X])|\leq\epsilon NR/2$.

#### Proof of Lemma 2.4: concentration around $\mathbb{E}[g(X)]$ via
martingales.

To show that $g(X)$ is concentrated around its mean, we show that $g$ is
sufficiently Lipschitz (w.r.t. the $\ell_{1}$ distance in
$\mathbb{R}_{+}^{C^{\prime}}$), and then apply standard martingale tools.

######  Claim 3.

The function $g$ is $R$-Lipschitz w.r.t. the $\ell_{1}$ distance in
$\mathbb{R}_{+}^{C^{\prime}}$.

######  Proof 2.6.

Fix a client $c\in C^{\prime}$, and consider two vectors
$\mathbf{d},\mathbf{d}^{\prime}\in\mathbb{R}_{+}^{C^{\prime}}$ with
$\mathbf{d}^{\prime}=\mathbf{d}+\delta\cdot\mathbbm{1}_{c}$. By definition of
FlowInstance, the only difference between
$\textup{{FlowInstance}}(\mathbf{d})$ and
$\textup{{FlowInstance}}(\mathbf{d}^{\prime})$ is that in
$\textup{{FlowInstance}}(\mathbf{d}^{\prime})$, client $c$ has $\delta$ more
demand and “special client” $f^{\prime}$ has $\delta$ less demand. Therefore,
if we begin with the min-cost flow of $\textup{{FlowInstance}}(\mathbf{d})$,
and then add $\delta$ units of flow from $c$ to $f^{\prime}$, then we now have
a feasible flow for $\textup{{FlowInstance}}(\mathbf{d}^{\prime})$.333We
define demand so that if a vertex $v$ has $d>0$ demand, then $d$ flow must
exit $v$ in a feasible flow, and if it has $d<0$ demand, then $|d|$ flow must
enter $v$. This means that

$g(\mathbf{d}^{\prime})\leq g(\mathbf{d})+\delta R.$

Similarly, starting from a min-cost flow of
$\textup{{FlowInstance}}(\mathbf{d}^{\prime})$ and then adding $\delta$ units
of flow from $f^{\prime}$ to $c$, we obtain a feasible flow for
$\textup{{FlowInstance}}(\mathbf{d})$, so

$g(\mathbf{d})\leq g(\mathbf{d}^{\prime})+\delta R.$

Together, these two inequalities show that $g$ is $R$-Lipschitz.

We state the following Chernoff bound for Lipschitz functions, which can be
proven by adapting the standard (multiplicative) Chernoff bound proof to a
martingale.

######  Theorem 2.7.

Let $x_{1},\ldots,x_{n}$ be independent random variables taking value $b$ with
probability $p$ and value $0$ with probability $1-p$, and let
$g:[0,1]^{n}\to\mathbb{R}$ be a $L$-Lipschitz function in $\ell_{1}$ norm.
Define $X:=(x_{1},\ldots,x_{n})$ and $\mu:=\mathbb{E}[g(X)]$. Then, for
$0\leq\epsilon\leq 1$:

$\Pr\big{[}\big{|}g(X)-\mathbb{E}[g(X)]\big{|}\geq\epsilon pnbL\big{]}\leq
2e^{-\epsilon^{2}pn/3}$

We apply Theorem 2.7 on the $L$-Lipschitz function $g$ with the randomly
sampled demands. Set $p:=r/N$ as the sampling probability, so that
$X\in\\{0,1/p\\}^{N}$ is the random demand vector. Setting $n:=N$, $b:=1/p$,
and $L:=R$, we obtain

$\displaystyle\Pr$
$\displaystyle\big{[}\big{|}g(X)-\mathbb{E}[g(X)]\big{|}\geq(\epsilon/2)NR\big{]}$
$\displaystyle=\Pr\big{[}\big{|}g(X)-\mathbb{E}[g(X)]\big{|}\geq(\epsilon/2)pnbL]$
$\displaystyle\leq 2\exp\left(\frac{-(\epsilon/2)^{2}pn}{3}\right)$
$\displaystyle=2\exp\left(\frac{-(\epsilon/2)^{2}(r/N)N}{3}\right)=\exp\left(-\Theta(\epsilon^{2}r)\right)=\exp\left(-\Omega(\epsilon^{2}\cdot\frac{k\log
n}{\epsilon^{2}})\right)$ $\displaystyle\leq n^{-(k+20)}$

for sufficiently large $\gamma$ in the definition of $r=\gamma k\log
n/\epsilon^{2}$. This concludes Lemma 2.4.

#### Proof of Lemma 2.5: relating $\mathbb{E}[g(X)]$ with $g(\mathbb{E}[X])$.

We have obtained concentration about $\mathbb{E}[g(X)]$, but we really need
concentration around $g(\mathbb{E}[X])=\textup{{CapKMed}}(C^{\prime},F)$. We
establish this by proving Lemma 2.5.

We first show the easy direction, that $g(\mathbb{E}[X])\leq\mathbb{E}[g(X)]$,
which essentially follows from the convexity of min-cost flow: Suppose the
outcomes of random variable $X$ are $\mathbf{d}_{1},\mathbf{d}_{2},\ldots$
with respective probabilities $\mu_{1},\mu_{2},\ldots$, so that
$\mathbb{E}[g(X)]=\sum_{i}\mu_{i}g(\mathbf{d}_{i})$. Now consider the flow
obtained by adding up, for each $i$, the min-cost flow of
$\textup{{FlowInstance}}(\mathbf{d}_{i})$ scaled by $\mu_{i}$. This flow is a
feasible flow to $\textup{{FlowInstance}}(\mathbb{E}[X])$ and has cost at most
$\mathbb{E}[g(X)]$. Since the min-cost flow of
$\textup{{FlowInstance}}(\mathbb{E}[X])$ can only be lower, we have
$g(\mathbb{E}[X])\leq\mathbb{E}[g(X)]$.

We now prove the other direction: $\mathbb{E}[g(X)]\leq
g(\mathbb{E}[X])+\epsilon NR/2$.

######  Claim 4.

With probability $1$, $g(X)\leq g(\mathbb{E}[X])+nNR$.

######  Proof 2.8.

Since $X\in[0,N/r]^{N}$, and since $g$ is $R$-Lipschitz, the entire range of
$g(X)$ is contained in some interval of length $N\cdot N/r\cdot R\leq N\cdot
n\cdot R$. Since $\mathbb{E}[X]\in[0,N/r]^{N}$ as well, the value
$g(\mathbb{E}[X])$ is also contained in that interval. The statement follows.

######  Lemma 2.9.

With probability $\geq 1-n^{-10}$, $g(X)\leq g(\mathbb{E}[X])+0.49\epsilon
NR$.

Due to space constraints, the proof of Lemma 2.9, which is long and technical,
is deferred to the full version. Assuming Lemma 2.9, we now show how Claim 4
and Lemma 2.9 together imply Lemma 2.5: we have

$\displaystyle\mathbb{E}[g(X)]$ $\displaystyle\leq
n^{-10}\cdot\big{(}g(\mathbb{E}[X])+nNR\big{)}+(1-n^{-10})\big{(}g(\mathbb{E}[X])+0.49\epsilon
NR\big{)}$ $\displaystyle=g(\mathbb{E}[X])+\big{(}n^{-10}\cdot
n+(1-n^{-10})\cdot 0.49\epsilon\big{)}NR$ $\displaystyle\leq
g(\mathbb{E}[X])+(\epsilon/2)NR,$

finishing the proof of Lemma 2.5.

###  2.2 $(3+\epsilon)$\- and $(9+\epsilon)$-approximation – Proof of Theorem
1.1

In this section, we finish the algorithm for Theorem 1.1. We will focus mainly
on the $k$-median case, since the $k$-means case is nearly identical.

Suppose we run the coreset for the capacitated $k$-median instance with
parameter $\epsilon_{0}$ (to be set later), obtaining a coreset $W\subseteq
C\times\mathbb{R}^{+}$ of size $\textup{poly}(k\log n\,\epsilon_{0}^{-1})$. We
now want to compute some $F\subseteq\mathbb{F}$ of size $k$ and an assignment
$\mu$ of the clients in $W$ to $F$ minimizing $\sum_{(c,w)\in W}w\cdot
d(c,\mu(c))$. By definition of coreset, if we compute an
$\alpha$-approximation to this problem, then we compute a
$(1+\epsilon_{0})\alpha$-approximation to the original capacitated $k$-median
problem.

The strategy is similar to that in [11]: we guess a set of _leaders_ and
_distances_ that match the optimal solution. More formally, let
$F^{*}=\\{f_{1}^{*},\ldots,f_{k}^{*}\\}\subseteq\mathbb{F}$ be the optimal
solution with assignment $\mu^{*}$. For each $f_{i}^{*}\in F^{*}$, let
$(\mu^{*})^{-1}(f_{i}^{*})$ be the clients in the coreset assigned by
$\mu^{*}$ to $f_{i}^{*}$, and let $\ell_{i}$ be the client in
$(\mu^{*})^{-1}(f_{i}^{*})$ closest to $f_{i}^{*}$. We call $\ell_{i}$ the
_leader_ of the client set $(\mu^{*})^{-1}(f_{i}^{*})$. Also, let $R_{i}$ be
the distance $d(f_{i}^{*},\ell_{i})$, rounded down to the closest integer
power of $(1+\epsilon_{1})$ for some $\epsilon_{1}$ we set later.

The algorithm begins with an enumeration phase. There are $|W|^{k}$ choices
for the set $\\{\ell_{1},\ldots,\ell_{k}\\}$, and $O(\epsilon_{1}^{-1}\log
n)^{k}$ choices for the values $R_{1},\ldots,R_{k}$, since we assumed that the
instance has aspect ratio $\textup{poly}(n)$. So by enumerating over
$|W|^{k}O(\epsilon_{1}^{-1}\log n)^{k}=(k\log
n\,\epsilon_{0}^{-1}\epsilon_{1}^{-1})^{O(k)}$ choices, we can assume that we
have guessed the right values $\ell_{i}$ and $R_{i}$.

For each leader $\ell_{i}$, define $\mathbb{F}_{i}$ as the centers
$f\in\mathbb{F}$ satisfying $d(\ell_{i},f)\in[1,1+\epsilon_{1})\cdot R_{i}$.
Note that $f_{i}^{*}\in\mathbb{F}_{i}$ for each $i$. Next, the algorithm wants
to pick the center in each $\mathbb{F}_{i}$ with the largest capacity. This
way, even if it doesn’t pick $f^{*}_{i}$ for $\mathbb{F}_{i}$, it picks a
center not much farther away that has at least as much capacity.

The most natural solution is to _greedily_ choose the center with largest
capacity in each $\mathbb{F}_{i}$. One immediate issue with this approach is
that we might choose the same center twice, since the sets $\mathbb{F}_{i}$
are not necessarily disjoint. Note that this issue is not as pronounced in the
uncapacitated $k$-median problem, since in that case, we can always imagine
choosing the same center twice and then throwing out one copy, which changes
nothing. In the capacitated case, choosing the same center twice effectively
doubles the capacity at that center, so throwing out a copy affects the
capacity at that center.

One simple fix to this issue is the simple idea of _color-coding_ , common in
the FPT literature: for each center $f\in\mathbb{F}$, independently assign a
uniformly random label in $\\{1,2,3,\ldots,k\\}$. With probability $1/k^{k}$,
each $f^{*}_{i}\in F^{*}$ is assigned label $i$. Moreover, repeating this
routine $O(k^{k}\log n)$ times ensures that w.h.p., this will happen in some
iteration. So with a $O(k^{k}\log n)$ multiplicative overhead in the running
time, we may assume that each $f^{*}_{i}$ is assigned label $i$.

The algorithm now chooses, from each $\mathbb{F}_{i}$, the center with the
largest capacity among all centers with label $i$. Since $f^{*}_{i}$ is an
option for each $\mathbb{F}_{i}$, the center chosen can only have larger
capacity. Let the center chosen from $\mathbb{F}_{i}$ be $f_{i}$. Let
$F:=\\{f_{1},\ldots,f_{k}\\}$ be our chosen centers.

We now claim that $F$ is a $(3+\epsilon_{1})$-approximation. Recall $\mu^{*}$,
the optimal assignment to the centers $F^{*}$; we construct an assignment
$\mu$ to $F$ as follows: for each client $c$ in the coreset, if $\mu^{*}$
assigns $c$ to center $f^{*}_{i}$, then we set $\mu(c)=f_{i}$. Observe that if
$\mu^{*}(c)=f^{*}_{i}$, then

$d(c,f_{i})\leq d(c,f^{*}_{i})+d(f^{*}_{i},\ell_{i})+d(\ell_{i},f_{i})\leq
d(c,f^{*}_{i})+2(1+\epsilon_{1})R_{i}\leq
d(c,f^{*}_{i})+2(1+\epsilon_{1})\cdot d(c,f^{*}_{i}),$

where the first inequality follows from triangle inequality, the second
follows since both $f^{*}_{i}$ and $f_{i}$ are approximately $R_{i}$ away from
$\ell_{i}$, and the third follows from $d(c,f^{*}_{i})\geq
d(\ell_{i},f^{*}_{i})\geq R$ by our choice of $\ell_{i}$. Therefore, we have
$d(c,\mu(c))=d(c,f_{i})\leq(3+2\epsilon_{1})d(c,f^{*}_{i})=(3+2\epsilon_{1})d(c,\mu^{*}(c))$.
Altogether, the total cost of the assignment $\mu$ is

$\sum_{(c,w)\in W}w\cdot d(c,\mu(c))\leq\sum_{(c,w)\in
W}w\cdot(3+2\epsilon_{1})d(c,\mu^{*}(c))=(3+2\epsilon_{1})\,OPT.$

The optimal assignment can only be better, hence the
$(3+2\epsilon_{1})$-approximation. This implies a
$(1+\epsilon_{0})(3+2\epsilon_{1})$-approximation in time $\textup{poly}(k\log
n\,\epsilon_{0}^{-1}\epsilon_{1}^{-1})^{O(k)}$. Finally, setting
$\epsilon_{0},\epsilon_{1}:=\Theta(\epsilon)$, for $\Theta(\cdot)$ small
enough, guarantees a $(3+\epsilon)$-approximation in time $(k\log
n\,\epsilon^{-1})^{O(k)}n^{O(1)}$.

Lastly, we show that the $(\log n)^{O(k)}$ factor in the running time can be
upper bounded by $k^{O(k)}n^{O(1)}$, proving the second running time in
Theorem 1.1. If $k<\frac{\log n}{\log\log n}$, then $(\log n)^{O(k)}=(\log
n)^{\frac{\log n}{\log\log n}}=n^{O(1)}$; otherwise, $k>\frac{\log n}{\log\log
n}\geq\sqrt{\log n}$, so $(\log n)^{O(k)}\leq(k^{2})^{O(k)}$. Therefore, the
running time in Theorem 1.1 is at most $O(k/\epsilon)^{O(k)}n^{O(1)}$.

For $k$-means, the algorithm and analysis are identical, except that the total
cost is now

${}_{(c,w)\in W}w\cdot d(c,\mu(c))^{2}\leq\sum_{(c,w)\in
W}w\cdot\big{(}(3+2\epsilon_{1})d(c,\mu^{*}(c))\big{)}^{2}=(9+O(\epsilon_{1}))\,OPT,$

implying a $(9+\epsilon)$-approximation. This concludes the proof of Theorem
1.1.

##  3 A $(1+\epsilon)$-Approximation for Euclidean Inputs

###  3.1 The Continuous (Uniform-Capacity) Case – Proof of Theorem 1.3

In this section we consider the continuous case: namely the case where centers
can be located at arbitary position in $\mathbb{R}^{d}$ and the capacities are
uniform and $\eta\geq n/k$.

Let $\epsilon>0$. Given a set of points $P$, denote by $\text{OPT}_{1}(P)$ the
location of the optimal center of $P$ (namely, the centroid of $P$ in the case
of the $k$-means problem or the median of $P$ in the case of the $k$-median
problem). We will make us of the following lemma of [20].

######  Lemma 3.1 (Lemma 5.3 in [20]).

Let $P$ be a set of points in $\mathbb{R}^{d}$ and $X$ be a random sample of
size $O(\epsilon^{-3}\log(1/\epsilon))$ from $P$ and $a$ and $b$ such that
$a\leq\textup{{cost}}(P,\text{OPT}_{1}(P))\leq b$. Then, we can construct a
set $Y$ of $O(2^{1/\epsilon^{O(1)}}\log(b/\epsilon a))$ points such that with
constant probability there is at least one point $z\in X\cup Y$ satisfying
$\textup{{cost}}(P,\\{z\\})\leq(1+2\epsilon)\textup{{cost}}(P,\text{OPT}_{1}(P))$.
Further, the time taken to construct $Y$ from $X$ is
$O(2^{1/\epsilon^{O(1)}}\log(b/\epsilon a)d)$.

Our algorithm for obtaining a $(1+\epsilon)$-approximation is as follows:

  1. 1.

Compute a coreset $C$ for capacitated $k$-median as described by Lemma 3.1,
and an estimate $\gamma$ of the value of OPT using the classic $O(\log
n)$-approximation.

In the remaining, we assume that the minimum pairwise distance between pairs
of points of $C$ is at least $\epsilon\gamma/(n\log n)$ since otherwise one
can simply take a net of the input and the additive error is at most
$\epsilon\text{OPT}$ (see e.g.: [11]). Moreover, we assume that there is no
cluster containing only one point of the coreset since these clusters can be
“guessed” and dealt with separately.

  2. 2.

Start with $\mathcal{C}=\emptyset$, then for each subset $S$ of $C$ of size
$O(\epsilon^{-3}\log(k/\epsilon))$, for each $s=(1+\epsilon)^{i}$ in the
interval $[\epsilon\gamma/(n\log n),\gamma]$ apply the procedure of Lemma 3.1
with $a=s$ and $b$ = $(1+\epsilon)a$ and add the output of the procedure to
$\mathcal{C}$. We refer to $\mathcal{C}$ as a set of approximate candidate
centers.

  3. 3.

Consider all subsets of size $k$ of $\mathcal{C}$. For each subset, compute
the cost of using this set of centers for the capacitated $k$-median instance
by using a min cost flow computation. Output the set of centers of minimum
cost.

We first discuss the running time of the algorithm. The time for computing the
coreset is polynomial by Theorem 2.1. Generating $\mathcal{C}$ takes
$|C|^{O(\epsilon^{-3}\log(1/\epsilon))}\cdot
2^{1/\epsilon^{O(1)}}\log((1+\epsilon)/\epsilon)d$ time. For the last part,
namely enumerating all subsets of $\mathcal{C}$ of size $k$, the running time
is $|C|^{O(k\epsilon^{-3}\log(1/\epsilon))}\cdot
2^{k/\epsilon^{O(1)}}\log^{k}((1+\epsilon)/\epsilon)$. Theorem 2.1 implies
that $|C|=\text{poly}(k\log n\,\epsilon^{-1})$ and so, the algorithm has
running time $(k\log n\,\epsilon^{-1})^{k\epsilon^{-O(1)}}n^{O(1)}$. Again,
the $(\log n)^{k\epsilon^{-O(1)}}$ factor can be upper bounded by
$(k/\epsilon)^{k\epsilon^{-O(1)}}$ or $n^{O(1)}$ based on whether or not
$k\epsilon^{-O(1)}<\frac{\log n}{\log\log n}$, hence the improved running time
in Theorem 1.3.

We show that this algorithm provides a $(1+O(\epsilon))$-approximation.
Theorem 2.1 immediately implies that the solution found for the coreset $C$
can be lifted to a solution for the original input at a cost of an additive
$O(\epsilon\text{OPT})$. For any (possibly weighted) set of client $A$ and set
of centers $B$, we define $\textup{{cost}}(A,B)$ to be the cost of the best
assignment of the clients in $A$ to the centers of $B$.

######  Lemma 3.2.

The $\mathcal{C}$ computed by the algorithm contains a set of centers
$\tilde{S}$ that is such that
$\textup{{cost}}(C,\tilde{S})\leq(1+\epsilon)\textup{{cost}}(C,\text{OPT})$.

######  Proof 3.3.

This follows almost immediately from Lemma 3.1. By Lemma 3.1, for each cluster
$C_{i}^{*}$ of OPT, there exists a set $S_{i}^{*}\subseteq C_{i}^{*}$ of size
at most $O(\epsilon^{-3}\log(k/\epsilon))$ such that applying the procedure of
Lemma 3.1 with the correct value of $a$ to $S_{i}^{*}$ yields a set of points
containing a point $z_{i}$ such that
$\textup{{cost}}(C_{i}^{*},z_{i})\leq(1+2\epsilon)\textup{{cost}}(C_{i}^{*},\text{OPT})$.
Since the algorithm iterates over all subsets of size
$O(\epsilon^{-3}\log(k/\epsilon))$, and that the pairwise distance is at least
$\epsilon\text{OPT}/n$, it follows that $S_{i}^{*}$ is one of the subset
considered by the algorithm, and so $z_{i}$ is part of $\mathcal{C}$.

Finally, since the algorithm iterates over all subsets of $\mathcal{C}$ of
size at most $k$, Lemma 3.2 implies that there exists a set
$\\{z_{1},\ldots,z_{k}\\}$ that is considered by the algorithm and on which
solving a min cost flow instance yields a solution of cost at most
$(1+O(\epsilon))\textup{{cost}}(\mathcal{P},\text{OPT})$.

###  3.2 The Non-Uniform Case – Proof of Theorem 1.2

We now consider the non-uniform case. In this setting, the input consists of a
set of points in $\mathbb{R}^{d}$ together with a set of candidate centers in
$\mathbb{R}^{d}$ and a capacity $\eta_{f}$ for each such candidate center. We
make use of the following lemma. As slightly worse bound for the lemma can
also be found in [25].

######  Lemma 3.4 ([27]).

Let $\epsilon\in(0,1)$ and $X\subseteq\mathbb{R}^{d}$ be arbitrary with $X$
having size $n>1$. There exists $f:\mathbb{R}^{d}\mapsto\mathbb{R}^{m}$ with
$m=O(\epsilon^{-2}\log n)$ such that $\forall x\in X$, $\forall
y\in\mathbb{R}^{d}$,
$||x-y||_{2}\leq||f(x)-f(y)||_{2}\leq(1+\epsilon)||x-y||_{2}$.

We describe a polynomial-time approximation scheme. Let $\epsilon>0$. The
algorithm is as follows. The first step of the algorithm is identical to the
continous case.

  1. 1.

Compute a coreset $C$ for capacitated $k$-median as described by Theorem 3.1,
and an estimate $\gamma$ of the value of OPT using the classic $O(\log
n)$-approximation.

In the remaining, we assume that the minimum pairwise distance between pairs
of points of $C$ is at least $\epsilon\gamma/(n\log n)$ since otherwise one
can simply take a net of the input and the additive error is at most
$\epsilon\text{OPT}$ (see e.g.: [11]). Moreover, we assume that there is no
cluster containing only one point of the coreset since these clusters can be
“guessed” and dealt with separately.

  2. 2.

Apply Lemma 3.4 to the points of the coreset to obtain a set of points in a
Euclidean space of dimension $\frac{\log k+\log\log n}{\epsilon^{O(1)}}$. Let
$C^{*}$ and $A^{*}$ be respectively the image of the coreset points and of the
candidate centers through the projection.

  3. 3.

Start with $\mathcal{V}=\emptyset$ For each point $p$ of the coreset do the
following: For each $i\in\\{1,2,\ldots,n^{2}\\}$, consider the $i$th-_ring_
defined by $\textup{{ball}}(p,(1+\epsilon)^{i}\epsilon\gamma/(n\log
n))\setminus\textup{{ball}}(p,(1+\epsilon)^{i-1}\epsilon\gamma/(n\log n))$ and
choose an $\epsilon\cdot(1+\epsilon)^{i}\epsilon\gamma/(n\log n)$-net.
Consider the Voronoi diagram induced by the points of the net. Then, for each
Voronoi cell, add to $\mathcal{V}$ the $k$ candidate centers of $A^{*}$ in the
cell that are of maximum capacity.

  4. 4.

Enumerate all possible subset of $\mathcal{V}$ of size $k$ and output the one
that leads to the solution of minimum cost.

#### Correctness.

Theorem 2.1 implies that finding a near-optimal solution for the coreset
points yields a near-optimal solution for the input point set.

Lemma 3.4 immediately implies that, given the coreset construction $C$, and
the projection of the coreset points onto a $\frac{\log k+\log\log
n}{\epsilon^{O(1)}}$-dimensional Euclidean space, finding a near-optimal set
of centers in $A^{*}$ yields a near-optimal set of centers in $A$ through the
inverse of the projection.

Therefore, it remains to show that the set $\mathcal{V}$ contains a set of
candidate centers that yields a near-optimal solution. To see this, consider
each center of the optimal solution in $A^{*}$. For each such optimal center
$f$, consider the closest coreset point $c(f)$ together with the ring of
$c(f)$ containing $f$. Let $j$ be the index of this ring, namely
$f\in\textup{{ball}}(p,(1+\epsilon)^{j}\epsilon\gamma/(n\log
n))\setminus\textup{{ball}}(p,(1+\epsilon)^{j-1}\epsilon\gamma/(n\log n))$.

By definition of the net, there exists a point $p$ of the net at distance at
most $\epsilon\cdot\textup{{ball}}(p,(1+\epsilon)^{j}\epsilon\gamma/(n\log
n))\leq 2\epsilon||c-c(f)||_{2}$ from $c(f)$. Therefore, consider the Voronoi
cell of $p$ and the top-$k$ candidate centers in terms of capacity. If $f$ is
part of this top-$k$, then $f$ is part of $\mathcal{V}$ and we are done.
Otherwise, it is possible to associate to $f$ a center $f^{*}$ that has
capacity at least the capacity of $f$, and so for all the optimal centers
simultaneously since we consider the top-$k$. Therefore, consider replacing
$f$ by $f^{*}$ in the optimal solution. The change in cost is at most, by the
triangle inequality, $4\epsilon||c-c(f)||_{2}$ since both centers are in the
Voronoi cell of $p$. Finally, since $c$ is the closest client to $c(f)$, the
cost increases by a factor at most $(1+4\epsilon)$ for each client and the
correctness follows.

#### Running time.

We now bound the running time. The first two steps are clearly polynomial
time. An $\epsilon\cdot(1+\epsilon)^{i}\epsilon\gamma/(n\log n)$-net of a ball
of radius $(1+\epsilon)^{i}\epsilon\gamma/(n\log n)$ has size
$\epsilon^{-O(d)}$ and so in this context, after Step 2, a size
$\epsilon^{-(\frac{\log k+\log\log n}{\epsilon^{O(1)}})}$. Since for each
element of the net, $k$ centers are chosen and since the number of rings is,
by Step 1, at most $O(\epsilon^{-2}\log n)$, the total size of $\mathcal{V}$
is at most $|C|k\epsilon^{-2}\log n\epsilon^{-(\frac{\log k+\log\log
n}{\epsilon^{O(1)}})}$ which is at most $|C|\epsilon^{-2}(k\log
n)^{\epsilon^{-O(1)}}=(k\epsilon^{-1}\log n)^{\epsilon^{-O(1)}}$. Enumerating
all subsets of size $k$ takes time $(k\epsilon^{-1}\log
n)^{k\epsilon^{-O(1)}}$ and the theorem follows.

## References

  * [1] M. Adamczyk, J. Byrka, J. Marcinkowski, S. M. Meesum, and M. Włodarczyk.  Constant factor FPT approximation for capacitated k-median.  ArXiv e-prints, September 2018.  arXiv:1809.05791.
  * [2] Sanjeev Arora, Prabhakar Raghavan, and Satish Rao.  Approximation schemes for Euclidean _k_ -medians and related problems.  In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 106–113, 1998\.  URL: http://doi.acm.org/10.1145/276698.276718, doi:10.1145/276698.276718.
  * [3] Jarosław Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase.  Bi-factor approximation algorithms for hard capacitated k-median problems.  In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 722–736. SIAM, 2014.
  * [4] Jarosław Byrka, Bartosz Rybicki, and Sumedha Uniyal.  An approximation algorithm for uniform capacitated k-median problem with $1+\epsilon$ capacity violation.  In International Conference on Integer Programming and Combinatorial Optimization, pages 262–274. Springer, 2016.
  * [5] Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha.  Rounding via trees: Deterministic approximation algorithms for group steiner trees and k-median.  In STOC, volume 98, pages 114–123. Citeseer, 1998.
  * [6] Moses Charikar, Sudipto Guha, Éva Tardos, and David B Shmoys.  A constant-factor approximation algorithm for the k-median problem.  Journal of Computer and System Sciences, 65(1):129–149, 2002.
  * [7] K. Chen.  On coresets for k-median and k-means clustering in metric and Eluclidean spaces and their applications.  SIAM Journal on Computing, 39(3):923–947, 2009.
  * [8] Julia Chuzhoy and Yuval Rabani.  Approximating k-median with non-uniform capacities.  In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05, pages 952–958, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics.  URL: http://dl.acm.org/citation.cfm?id=1070432.1070569.
  * [9] Vincent Cohen-Addad.  Approximation schemes for capacitated clustering in doubling metrics.  CoRR, abs/1812.07721, 2018.  URL: http://arxiv.org/abs/1812.07721, arXiv:1812.07721.
  * [10] Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, and Alan Roytman.  The bane of low-dimensionality clustering.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 441–456, 2018.  doi:10.1137/1.9781611975031.30.
  * [11] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li.  Tight FPT approximations for k-median and k-means.  In ICALP 2019, 2019.
  * [12] Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani.  Approximation schemes for clustering problems.  In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 50–58. ACM, 2003.  URL: http://doi.acm.org/10.1145/780542.780550, doi:10.1145/780542.780550.
  * [13] H. Gökalp Demirci and Shi Li.  Constant approximation for capacitated k-median with (1+epsilon)-capacity violation.  In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 73:1–73:14, 2016\.  doi:10.4230/LIPIcs.ICALP.2016.73.
  * [14] G. Frahling and C. Sohler.  Coresets in dynamic geometric data streams.  In STOC, pages 209–217, 2005.
  * [15] Anupam Gupta, Euiwoong Lee, and Jason Li.  An fpt algorithm beating 2-approximation for k-cut.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, pages 2821–2837, Philadelphia, PA, USA, 2018\. Society for Industrial and Applied Mathematics.  URL: http://dl.acm.org/citation.cfm?id=3174304.3175483.
  * [16] Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, and Michal Wlodarczyk.  Losing treewidth by separating subsets.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1731–1749, 2019.  doi:10.1137/1.9781611975482.104.
  * [17] Sariel Har-Peled and Akash Kushal.  Smaller coresets for k-median and k-means clustering.  Discrete & Computational Geometry, 37(1):3–19, 2007.  URL: http://dx.doi.org/10.1007/s00454-006-1271-x, doi:10.1007/s00454-006-1271-x.
  * [18] Sariel Har-Peled and Soham Mazumdar.  On coresets for k-means and k-median clustering.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 291–300, 2004.  URL: http://doi.acm.org/10.1145/1007352.1007400, doi:10.1145/1007352.1007400.
  * [19] Amit Kumar, Yogish Sabharwal, and Sandeep Sen.  A simple linear time (1+ ") -approximation algorithm for k-means clustering in any dimensions.  In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’04, pages 454–462, Washington, DC, USA, 2004. IEEE Computer Society.  URL: http://dx.doi.org/10.1109/FOCS.2004.7, doi:10.1109/FOCS.2004.7.
  * [20] Amit Kumar, Yogish Sabharwal, and Sandeep Sen.  Linear-time approximation schemes for clustering problems in any dimensions.  J. ACM, 57(2), 2010.  URL: http://doi.acm.org/10.1145/1667053.1667054, doi:10.1145/1667053.1667054.
  * [21] Euiwoong Lee.  Partitioning a graph into small pieces with applications to path transversal.  Mathematical Programming, Mar 2018.  doi:10.1007/s10107-018-1255-7.
  * [22] Shi Li.  On uniform capacitated k-median beyond the natural LP relaxation.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 696–707, 2015.  doi:10.1137/1.9781611973730.47.
  * [23] Shi Li.  Approximating capacitated _k_ -median with (1 + _k_ open facilities.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 786–796, 2016.  doi:10.1137/1.9781611974331.ch56.
  * [24] Shi Li.  On uniform capacitated _k_ -median beyond the natural LP relaxation.  ACM Trans. Algorithms, 13(2):22:1–22:18, 2017.  URL: http://doi.acm.org/10.1145/2983633, doi:10.1145/2983633.
  * [25] Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn.  Nonlinear dimension reduction via outer bi-lipschitz extensions.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1088–1101, New York, NY, USA, 2018. ACM.  URL: http://doi.acm.org/10.1145/3188745.3188828, doi:10.1145/3188745.3188828.
  * [26] Dániel Marx and Michal Pilipczuk.  Optimal parameterized algorithms for planar facility location problems using voronoi diagrams.  In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 865–877, 2015.  doi:10.1007/978-3-662-48350-3_72.
  * [27] Shyam Narayanan and Jelani Nelson.  Optimal terminal dimensionality reduction in euclidean space.  CoRR – To appear in the proceedings of STOC’19, abs/1810.09250, 2018.  URL: http://arxiv.org/abs/1810.09250, arXiv:1810.09250.
  * [28] Yicheng Xu, Yong Zhang, and Yifei Zou.  A constant parameterized approximation for hard-capacitated k-means.  CoRR, abs/1901.04628, 2019.  URL: http://arxiv.org/abs/1901.04628, arXiv:1901.04628.

##  Appendix A Proof of Lemma 2.9

Our strategy is to construct a flow for $\textup{{FlowInstance}}(X)$ with cost
$\leq g(\mathbb{E}[X])+0.49\epsilon NR=g(\mathbbm{1})+0.49\epsilon NR$, and
ensure that it succeeds with probability $\geq 1-n^{-10}$. Essentially, we
want to look at the min-cost flow of $\textup{{FlowInstance}}(\mathbbm{1})$,
and construct a flow that is competitive to it.

First, for all clients not in $C^{\prime}$, we route their $1$ unit of demand
in the same manner as in the min-cost flow of
$\textup{{FlowInstance}}(\mathbbm{1})$. Therefore, it remains to assign the
demands in $C^{\prime}$, as well as the extra $N-\sum_{c\in C^{\prime}}d_{c}$
demand at ring center $f^{\prime}$.

Consider the optimal min-cost flow on $\textup{{FlowInstance}}(\mathbbm{1})$,
which we can assume is an integral flow. For each center $f\in F$, define
$C^{\prime}_{f}\subseteq C^{\prime}$ as the clients served by $f$ in this
flow. For each center $f$, we now focus on routing the demands of the sampled
clients in $C^{\prime}_{f}$. Let $S_{f}\subseteq C^{\prime}_{f}$ be the
sampled clients in $C^{\prime}_{f}$, i.e., the clients whose coordinates in
$X$ are nonzero. Note that $S_{f}$ is distributed as
$\textup{{Binomial}}(|C^{\prime}_{f}|,r/N)$. If $S_{f}\cdot
r/N\leq|C^{\prime}_{f}|$ (i.e., we under-sampled), then in
$\textup{{FlowInstance}}(X)$, we will route:

  1. (1)

$N/r$ units of flow from each center in $S_{f}$ to $f$, and

  2. (2)

$|C^{\prime}_{f}|-|S_{f}|\cdot N/r$ units of flow from ring center
$f^{\prime}$ to $f$.

Otherwise, if $S_{f}\cdot r/N>|C^{\prime}_{f}|$ (i.e., we over-sampled), then
we will first randomly sub-sample from $S_{f}$ to obtain a set
$S^{\prime}_{f}$ of size exactly $\lfloor|C^{\prime}_{f}|\cdot N/r\rfloor$,
and then apply steps (1) and (2) on $S^{\prime}_{f}$ instead of $S_{f}$, and
finally route the remaining $N/r$ units of flow from each client in
$S_{f}\setminus S^{\prime}_{f}$ to the ring center $f^{\prime}$. It is easy to
verify that if we do this for each $C^{\prime}_{f}$, we obtain a feasible flow
for $\textup{{FlowInstance}}(X)$.

While the flow construction is the same for each $C^{\prime}_{f}$, we will
case on whether $\mathbb{E}[|S_{f}|]=|C^{\prime}_{f}|\cdot r/N$ is above or
below $0.05\epsilon r/k$ in our analysis.

#### Case $\mathbb{E}[|S_{f}|]\geq 0.05\epsilon r/k$.

First, suppose that $\mathbb{E}[|S_{f}|]\geq 0.05\epsilon
r/k\iff|C^{\prime}_{f}|\geq 0.05\epsilon N/k$, considered to be the “hard”
case. We begin with a concentration bound on the size of $S_{f}$:

######  Subclaim A.1.

With probability $\geq 1-n^{-20}$,

$\left||S_{f}|-|C^{\prime}_{f}|\cdot\frac{r}{N}\right|\leq
0.1\epsilon\cdot|C^{\prime}_{f}|\cdot\frac{r}{N}.$

######  Proof A.2.

We apply the Chernoff bound

$\displaystyle\Pr\big{[}\big{|}|S_{f}|-|C^{\prime}_{f}|\cdot r/N\big{|}\leq
0.1\epsilon\cdot|C^{\prime}_{f}|\cdot r/N\big{]}$
$\displaystyle\leq\exp(-\Theta(\epsilon^{2}\cdot|C^{\prime}_{f}|\cdot r/N))$
$\displaystyle\leq\exp(-\Theta(\epsilon^{2}\cdot 0.05\epsilon r/k))$
$\displaystyle\leq\exp(-20\ln n)=n^{-20}$

for large enough $\gamma$ in the definition of $r$.

If $S_{f}>|C^{\prime}_{f}|\cdot N/r$, then let $S^{\prime}_{f}$ be the set
$S_{f}$ with $\big{\lceil}S_{f}-|C^{\prime}_{f}|\big{\rceil}$ random clients
removed; otherwise, let $S^{\prime}_{f}=S_{f}$. (So essentially, we are
merging the under-sampled and over-sampled cases together.) By construction,
$|S^{\prime}_{f}|\leq|C^{\prime}_{f}|\cdot r/N$, and by Subclaim A.1, with
probability $\geq 1-n^{-20}$,

$\displaystyle|S_{f}|-|S^{\prime}_{f}|\leq
0.1\epsilon\cdot|C^{\prime}_{f}|\cdot\frac{r}{N}+1\leq
0.11\epsilon\cdot|C^{\prime}_{f}|\cdot\frac{r}{N},$ (2)

that is, at most $0.11\epsilon\cdot|C^{\prime}_{f}|\cdot r/N$ many clients
were removed. Also, by Subclaim A.1,

$\displaystyle|C^{\prime}_{f}|\cdot\frac{r}{N}-|S^{\prime}_{f}|\leq
0.1\epsilon\cdot|C^{\prime}_{f}|\cdot\frac{r}{N}$ (3)

For each client $c\in S^{\prime}_{f}$, we route $N/r$ units of flow from $c$
to $f$, costing $N/r\cdot d(c,f)$. To bound the cost of the flow, we use the
following concentration bound from [Chen09]:

######  Lemma A.3 (Lemma 3.2 from Chen09).

Let $M\geq 0$ and $\eta$ be fixed constants, and let $h(\cdot)$ be a function
defined on a set $V$ such that $\eta\leq h(p)\leq\eta+M$ for all $p\in V$. Let
$U=\\{p_{1},\ldots,p_{s}\\}$ be a set of $s$ samples drawn independently and
uniformly from $V$, and let $\delta>0$ be a parameter. If
$s\geq(M^{2}/2\delta^{2})\ln(2/\lambda)$, then
$\Pr\big{[}\big{|}\frac{h(V)}{|V|}-\frac{h(U)}{|U|}\big{|}\geq\delta\big{]}\leq\lambda$,
where $h(U)=\sum_{u\in U}h(u)$ and $h(V)=\sum_{v\in V}h(v)$.

Fix an arbitrary integer $s\in[1-0.1\epsilon,1]\cdot|C^{\prime}_{f}|\cdot
r/N$, and for now, condition on the event that $|S^{\prime}_{f}|=s$. Observe
that under this conditioning, the clients in $S^{\prime}_{f}$ is a uniformly
random sample of $s$ clients in $C^{\prime}_{f}$. We apply this lemma with
$M:=2R$, $h(c):=d(c,f)$, $U:=S^{\prime}_{f}$, $V:=C^{\prime}_{f}$,
$\delta:=0.1\epsilon R$, $\lambda:=n^{-20}$. To verify the requirements of the
lemma, observe that

$\displaystyle s$ $\displaystyle\geq(1-0.1\epsilon)\cdot|C^{\prime}_{f}|\cdot
r/N\geq(1-0.1\epsilon)\cdot 0.05\epsilon N/k\cdot r/N=\Theta(\epsilon
r/k)=\Theta(k\log n/\epsilon^{2})$
$\displaystyle\geq(M^{2}/2\delta^{2})\ln(2/\lambda)$

for sufficiently large constant $\gamma$ in $r=\gamma k\log n/\epsilon^{3}$.
Also, since all clients in $C^{\prime}$ are within some ball of radius $R$, by
the triangle inequality, all values of $h(c)=d(c,f)$ are contained in an
interval of length $2R$, so the function $h$ satisfies the condition of the
lemma for some $\eta$. Therefore, we invoke Lemma A.3 to obtain that with
probability $\geq 1-n^{-20}$,

$\left|\frac{h(V)}{|V|}-\frac{h(U)}{|U|}\right|=\left|\frac{h(C^{\prime}_{f})}{|C^{\prime}_{f}|}-\frac{h(S^{\prime}_{f})}{|S^{\prime}_{f}|}\right|\leq\delta\iff\left|\frac{h(V)\cdot|S^{\prime}_{f}|}{|C^{\prime}_{f}|}-h(U)\right|\leq\delta|S^{\prime}_{f}|$
$\displaystyle\implies h(S^{\prime}_{f})$ $\displaystyle\leq
h(C^{\prime}_{f})\cdot\frac{|S^{\prime}_{f}|}{|C^{\prime}_{f}|}+\delta|S^{\prime}_{f}|$
$\displaystyle\leq
h(C^{\prime}_{f})\cdot\frac{|S^{\prime}_{f}|}{|C^{\prime}_{f}|}+\delta\left(|C^{\prime}_{f}|\cdot\frac{r}{N}\right)$
$\displaystyle\implies h(S^{\prime}_{f})\cdot\frac{N}{r}$ $\displaystyle\leq
h(C^{\prime}_{f})\cdot\frac{|S^{\prime}_{f}|}{|C^{\prime}_{f}|}\cdot\frac{N}{r}+\delta|C^{\prime}_{f}|$
$\displaystyle=h(C^{\prime}_{f})\cdot\frac{|S^{\prime}_{f}|}{|C^{\prime}_{f}|}\cdot\frac{N}{r}+0.1\epsilon
R|C^{\prime}_{f}|.$ (4)

Observe that $h(S^{\prime}_{f})\cdot N/r$ is exactly the cost of our flow in
step (1), and $h(C^{\prime}_{f})$ is exactly the cost of the flow paths to $f$
in the min-cost flow of $\textup{{FlowInstance}}(\mathbbm{1})$. Finally, we
take a union bound over all values of $s$.

Next, we bound the routing cost of step (2), namely, routing
$|C^{\prime}_{f}|-|S^{\prime}_{f}|\cdot N/r$ flow from ring center
$f^{\prime}$ to $f$. By the triangle inequality, for all clients $c\in
C^{\prime}_{f}\subseteq\textup{{ball}}(f^{\prime},R)$, we have
$d(f^{\prime},f)\leq d(c,f)+R=h(c)+R$. In particular, averaging gives
$d(f^{\prime},f)\leq h(C^{\prime}_{f})/|C^{\prime}_{f}|+R$. Therefore, the
total cost of step (2) is

$\displaystyle\left(|C^{\prime}_{f}|-|S^{\prime}_{f}|\cdot\frac{N}{r}\right)\cdot
d(f^{\prime},f)$
$\displaystyle\leq\left(|C^{\prime}_{f}|-|S^{\prime}_{f}|\cdot\frac{N}{r}\right)\cdot\left(\frac{h(C^{\prime}_{f})}{|C^{\prime}_{f}|}+R\right)$
$\displaystyle\leq
h(C^{\prime}_{f})-h(C^{\prime}_{f})\cdot\frac{|S^{\prime}_{f}|}{|C^{\prime}_{f}|}\cdot\frac{N}{r}+\left(|C^{\prime}_{f}|-|S^{\prime}_{f}|\cdot\frac{N}{r}\right)\cdot
R$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq:3})}}{{\leq}}h(C^{\prime}_{f})-h(C^{\prime}_{f})\cdot\frac{|S^{\prime}_{f}|}{|C^{\prime}_{f}|}\cdot\frac{N}{r}+0.1\epsilon\cdot|C^{\prime}_{f}|\cdot
R$ (5)

Finally, if we over-sampled the set $S^{\prime}_{f}$, then we need to route
$N/r$ flow from each client in $S_{f}\setminus S^{\prime}_{f}$ to the ring
center $f^{\prime}$. Since all clients in $C^{\prime}_{f}$ are distance $\leq
R$ from $f^{\prime}$, this costs at most

$\displaystyle(|S_{f}|-|S^{\prime}_{f}|)\cdot\frac{N}{r}\cdot
R\stackrel{{\scriptstyle(\ref{eq:2})}}{{\leq}}\left(0.11\epsilon\cdot|C^{\prime}_{f}|\cdot\frac{r}{N}\right)\cdot\frac{N}{r}\cdot
R\leq 0.11\epsilon\cdot|C^{\prime}_{f}|\cdot R.$ (6)

The total flow is the sum of (4), (5), and (6), which is at most

$h(C^{\prime}_{f})+0.31\epsilon R|C^{\prime}_{f}|=\sum_{c\in
C^{\prime}_{f}}d(c,f)+0.31\epsilon R|C^{\prime}_{f}|.$

#### Case $\mathbb{E}[|S_{f}|]\leq 0.05\epsilon r/k$.

Now suppose that $\mathbb{E}[|S_{f}|]\leq 0.05\epsilon
r/k\iff|C^{\prime}_{f}|\leq 0.05\epsilon N/k$. In this case, we have a
corresponding concentration bound, similar to Subclaim A.1, but this one is
one-sided and more generous:

######  Subclaim A.4.

With probability $\geq 1-n^{-20}$,

$|S_{f}|\leq 0.06\epsilon r/k.$

######  Proof A.5.

We apply the Chernoff bound

$\Pr[|S_{f}|\geq\mathbb{E}[|S_{f}|]+0.01\epsilon r/k]\leq\exp(-\Theta(\epsilon
r/k))\leq\exp(-20\ln n)=n^{-20}$

for large enough $\gamma$ in the definition of $r$.

We now compute the costs of the flows, analogous to the bounds of (4), (5),
and (6) in the other case; here, our bounds will be a lot looser. For (4), we
instead have

$\displaystyle\sum_{c\in S^{\prime}_{f}}d(c,f)\cdot\frac{N}{r}$
$\displaystyle\leq\sum_{c\in
S^{\prime}_{f}}(d(c,f^{\prime})+d(f^{\prime},f))\cdot\frac{N}{r}$
$\displaystyle\leq\sum_{c\in
S^{\prime}_{f}}(R+d(f^{\prime},f))\cdot\frac{N}{r}$
$\displaystyle=|S^{\prime}_{f}|\cdot(R+d(f^{\prime},f))\cdot\frac{N}{r};$

for (5), we instead have

$\displaystyle\left(|C^{\prime}_{f}|-|S^{\prime}_{f}|\cdot\frac{N}{r}\right)\cdot
d(f^{\prime},f)$ $\displaystyle=\sum_{c\in
C^{\prime}_{f}}d(f^{\prime},f)-|S^{\prime}_{f}|\cdot\frac{N}{r}\cdot
d(f^{\prime},f)$ $\displaystyle\leq\sum_{c\in
C^{\prime}_{f}}(d(f^{\prime},c)+d(c,f))-|S^{\prime}_{f}|\cdot\frac{N}{r}\cdot
d(f^{\prime},f)$ $\displaystyle\leq\sum_{c\in
C^{\prime}_{f}}(R+d(c,f))-|S^{\prime}_{f}|\cdot\frac{N}{r}\cdot
d(f^{\prime},f)$ $\displaystyle=|C^{\prime}_{f}|\cdot R+\sum_{c\in
C^{\prime}_{f}}d(c,f)-|S^{\prime}_{f}|\cdot\frac{N}{r}\cdot d(f^{\prime},f);$

and for (6), we instead have

$\displaystyle(|S_{f}|-|S^{\prime}_{f}|)\cdot\frac{N}{r}\cdot
R\leq|S_{f}|\cdot\frac{N}{r}\cdot R.$

Altogether, summing up these bounds gives a total flow at most

$\displaystyle\sum_{c\in C^{\prime}_{f}}d(c,f)+|S^{\prime}_{f}|\cdot
R\cdot\frac{N}{r}+|C^{\prime}_{f}|\cdot R+|S_{f}|\cdot\frac{N}{r}\cdot R$
$\displaystyle\leq\sum_{c\in C^{\prime}_{f}}d(c,f)+\frac{0.06\epsilon
r}{k}\cdot R\cdot\frac{N}{r}+\frac{0.05\epsilon N}{k}\cdot
R+\frac{0.06\epsilon r}{k}\cdot\frac{N}{r}\cdot R$ $\displaystyle=\sum_{c\in
C^{\prime}_{f}}d(c,f)+\frac{0.17\epsilon NR}{k}.$

#### Putting things together.

Regardless of case, the flow is upper bounded by

$\sum_{c\in C^{\prime}_{f}}d(c,f)+0.31\epsilon
R|C^{\prime}_{f}|+\frac{0.17\epsilon NR}{k}.$

Finally, summing over all $f\in F$, we obtain a total cost of at most

$\sum_{f\in F}\left(\sum_{c\in C^{\prime}_{f}}d(c,f)+0.31\epsilon
R|C^{\prime}_{f}|+\frac{0.17\epsilon NR}{k}\right)=\sum_{f\in F}\sum_{c\in
C^{\prime}_{f}}d(c,f)+0.31\epsilon R|C^{\prime}|+0.17\epsilon NR$

for routing all demands in $C^{\prime}$, as well as the extra demand at ring
center $f^{\prime}$. That is, our flow is only $0.48\epsilon NR$ additively
worse off at routing these demands, compared to the min-cost flow of
$\textup{{FlowInstance}}(\mathbbm{1})$. Lastly, since the two flows coincide
outside of these demands, Lemma 2.9 follows.

##  Appendix B Multiple rings case

Consider now the case of multiple rings. Our idea is to consider a single
martingale across all rings, but _bound the concentration for each ring
separately_ (and then take a union bound over all rings). We treat each ring
separately because the rings have varying scales, and martingale inequalities
are nicest when all random variables are on the same scale.

In particular, the rings in the martingale are ordered sequentially, so that
all vertices in the first ring appear first, then all vertices in the second
ring, etc. The ordering can be arbitrary, but for simplicity of analysis, let
us assume the ordering is lexicographic by $(i,R)$, with the $<$ comparison
operator on $(i,R)$ indicating lexicographic comparison.

We will now define a function $g_{i,R}$ for each ring $C_{i,R}$, similar to
the function $g$ from Section 2.1. Fix a ring $C_{i,R}$; the function
$g_{i,R}$ will depend on the samples $S_{i^{\prime},R^{\prime}}$ of all the
other rings, i.e., $S_{i^{\prime},R^{\prime}}$ for all
$(i^{\prime},R^{\prime})\neq(i,R)$. So suppose we fix the sample
$S_{i^{\prime},R^{\prime}}$ for all other rings. For input a vector
$\mathbf{d}\in\mathbb{R}_{+}^{C_{i,R}}$ (indexed by clients in $C_{i,R}$),
consider a min-cost flow instance $\textup{{FlowInstance}}_{i,R}(\mathbf{d})$
on the graph metric with the following demands. First, set demand $d_{c}$ at
each client $c\in C_{i,R}$ and demand $|C_{i,R}|-\sum_{c\in C_{i,R}}d_{c}$, as
in $\textup{{FlowInstance}}(\mathbf{d})$ in Section 2.1. Now, for each sample
$C_{i^{\prime},R^{\prime}}$, $(i^{\prime},R^{\prime})\neq(i,R)$, set demand
$|C_{i^{\prime},R^{\prime}}|/r$ at each client $c\in
S_{i^{\prime},R^{\prime}}$; note that
$|S_{i^{\prime},R^{\prime}}|\cdot|C_{i^{\prime},R^{\prime}}|/r=|C_{i^{\prime},R^{\prime}}|$,
so no additional demands needs to be set at ring center
$f^{\prime}_{i^{\prime}}$. Observe that
$\textup{{FlowInstance}}_{i,R}(\mathbf{d})$ is a feasible min-cost flow
instance.

The following is an analogue of Claim 3 from Section 2.1, and the proof is
identical:

######  Claim 5.

For any ring $C_{i,R}$ and fixed samples $S_{i^{\prime},R^{\prime}}$ for all
$(i^{\prime},R^{\prime})\neq(i,R)$, the function $g_{i,R}(\mathbf{d})$ is
$R$-Lipschitz w.r.t. the $\ell_{1}$ distance in $\mathbb{R}_{+}^{C_{i,R}}$.

Recall that the average of a set of $R$-Lipschitz functions is also
$R$-Lipschitz. Suppose now, we only fix the samples
$S_{i^{\prime},R^{\prime}}$ for $(i^{\prime},R^{\prime})<(i,R)$ and instead
take the expectation over $(i^{\prime},R^{\prime})>(i,R)$. Then, the expected
value of $g_{i,R}(\mathbf{d})$, that is,

$\displaystyle\mathbb{E}_{S_{i^{\prime},R^{\prime}}:(i^{\prime},R^{\prime})>(i,R)}\left[g_{i,R}(\mathbf{d})\big{|}S_{i^{\prime},R^{\prime}}:(i^{\prime},R^{\prime})<(i,R)\right],$
(7)

is also $R$-Lipschitz. From now on, we will abbreviate (7) with simply
$\mathbb{E}[g_{i,R}(\mathbf{d})]$, i.e., the expectation and conditioning are
implicit. We therefore obtain:

######  Claim 6.

For any ring $C_{i,R}$, $\mathbb{E}[g_{i,R}(\mathbf{d})]$ is $R$-Lipschitz
w.r.t. the $\ell_{1}$ distance in $\mathbb{R}_{+}^{C_{i,R}}$.

We now focus on the analogues of Lemmas 2.4 and 2.5, whose proofs follow
through when $g$ is replaced by $g_{i,R}$. The reasoning is that our arguments
are not affected by the nature of the demands outside the ones attributed to
$C_{i,R}$. For example, in the proof of Lemma 2.9, we route demands outside of
those attributed to $C_{i,R}$ in the same manner as the min-cost flow in
$\textup{{FlowInstance}}(\mathbbm{1})$, and this argument does not depend on
these particular demands.

######  Lemma B.1.

Assume that $|C_{i,R}|>\Theta(k\log n/\epsilon^{3})$. With probability $\geq
1-n^{-(k+20)}$, we have
$|g_{i,R}(X)-\mathbb{E}[g_{i,R}(X)]|\leq\epsilon|C_{i,R}|R/2$.

######  Lemma B.2.

Assume that $|C_{i,R}|>\Theta(k\log n/\epsilon^{3})$. Then,
$|\mathbb{E}[g_{i,R}(X)]-g_{i,R}(\mathbb{E}[X])|\leq\epsilon|C_{i,R}|R/2$.

The remaining arguments in Section 2.1, the ones that link Lemmas 2.4 and 2.5
to Lemma 2.3, also follow through. In particular, instead of Lemma 2.3, we are
now bounding the deviation of the random variable

$\mathbb{E}_{>(i,R)}\big{[}\textup{{FracCapKMed}}(W^{\prime},F)\big{]}:=\mathbb{E}_{S_{i^{\prime},R^{\prime}}:(i^{\prime},R^{\prime})>(i,R)}\left[\textup{{FracCapKMed}}(W^{\prime},F)\big{|}S_{i^{\prime},R^{\prime}}:(i^{\prime},R^{\prime})<(i,R)\right]$

from the constant

$\mathbb{E}_{\geq(i,R)}\big{[}\textup{{FracCapKMed}}(W^{\prime},F)\big{]}:=\mathbb{E}_{S_{i^{\prime},R^{\prime}}:(i^{\prime},R^{\prime})\geq(i,R)}\left[\textup{{FracCapKMed}}(W^{\prime},F)\big{|}S_{i^{\prime},R^{\prime}}:(i^{\prime},R^{\prime})<(i,R)\right].$

With these definitions in mind, Lemmas B.1 and B.2 together imply:

######  Lemma B.3.

W.h.p., for any set of $k$ centers $F\subseteq\mathbb{F}$ satisfying
$\textup{{CapKMed}}(C,F)<\infty$,

$\displaystyle\left|\mathbb{E}_{>(i,R)}\big{[}\textup{{FracCapKMed}}(W^{\prime},F)\big{]}-\mathbb{E}_{\geq(i,R)}\big{[}\textup{{FracCapKMed}}(W^{\prime},F)\big{]}\right|\leq\epsilon|C_{i,R}|R.$

Recall that there are only $O(k\log n)$ rings. Consider the process of going
through the rings $C_{i,R}$ in order, and for each one, apply Lemma B.3
conditioned on the choices of $S_{i^{\prime},R^{\prime}}$ for
$(i^{\prime},R^{\prime})<(i,R)$. W.h.p., for any set of $k$ centers
$F\subseteq\mathbb{F}$, the total deviation is at most
$\sum_{(i,R)}\epsilon|C_{i,R}|R$, that is,

$\displaystyle\left|\textup{{FracCapKMed}}(W^{\prime},F)-\mathbb{E}\big{[}\textup{{FracCapKMed}}(W^{\prime},F)\big{]}\right|\leq\sum_{(i,R)}\epsilon|C_{i,R}|R.$
(8)

It remains to bound $\sum_{(i,R)}\epsilon|C_{i,R}|R$ by $OPT$. Observe that
the bicriteria solution (line 1) has solution $O(OPT)$, and for each ring
$C_{i,R}$, pays $\sum_{c\in C_{i,R}}d(c,f_{i}^{\prime})\geq|C_{i,R}|\cdot
R/2$, using that $c\notin\textup{{ball}}(f^{\prime}_{i},R/2)$. Therefore,
continuing (8), we get

$\displaystyle\left|\textup{{FracCapKMed}}(W^{\prime},F)-\mathbb{E}\big{[}\textup{{FracCapKMed}}(W^{\prime},F)\big{]}\right|$
$\displaystyle\leq\sum_{(i,R)}\epsilon|C_{i,R}|R$
$\displaystyle=2\epsilon\cdot\sum_{(i,R)}|C_{i,R}|\cdot R/2$
$\displaystyle\leq 2\epsilon\cdot ALG^{\prime}\leq O(\epsilon)\cdot OPT.$

Finally, scaling down $\epsilon$ by a constant factor, so that
$O(\epsilon)\cdot OPT$ becomes $\epsilon\cdot OPT$, produces the desired
coreset, finishing Theorem 2.1.

##  Appendix C Coreset for $k$-means

The main technical difference in the $k$-means case is that we can no longer
view the problem as a formulation of FlowInstance from Section 2.1, even if we
square the distances. This is because FlowInstance does not stop a flow path
from using multiple short edges which, with each edge length squared, is a lot
smaller in total than the entire distance squared. Therefore, we instead
consider a bipartite matching formulation, where clients, which have positive
demand, are on the left (call them _sources_), and centers, which have
negative demand, are on the right (call them _sinks_). As for the potential
demand $N-\sum_{c\in C^{\prime}}d_{c}$ at ring center
$f^{\prime}=f^{\prime}_{i}$, if this demand is positive, then $f^{\prime}$ is
one the left (it becomes a source); if it is negative, then $f^{\prime}$ is on
the right (it becomes a sink). We will not give this modified instance a name,
since the rest of this section follows closely to Section 2.1.

###  C.1 Single-ring case ($k$-means)

For our single-ring case of the $k$-means coreset, we have the following
corresponding lemma. Observe that the bound is slightly worse: there is an
extra $O(\epsilon)\cdot OPT$ term in the error. This is not morally a problem,
since there are only $O(k\log n)$ rings, but it will make our overall core-set
bounds worse.

######  Lemma C.1.

W.h.p., for any set of $k$ centers $F\subseteq\mathbb{F}$ satisfying
$\textup{{CapKMeans}}(C,F)<\infty$,

$\displaystyle|\textup{{FracCapKMeans}}(W^{\prime},F)-\textup{{CapKMeans}}(C,F)|\leq\epsilon
NR+O(\epsilon)\cdot OPT.$ (9)

The proof of Lemma C.1 follows the outline of Section 2.1. The rest of this
section describes the modifications we make compared to Section 2.1.

#### Step (1).

We apply Lemma A.3 with a different set of parameters. This time, define
$h(c):=d(c,f)^{2}$ to capture $k$-means distance. Since all distances $d(c,f)$
for $f\in C^{\prime}_{f}$ are within an interval of length $2R$, the average
distance $\sum_{c\in C^{\prime}_{f}}d(c,f)/|C^{\prime}_{f}|$ also belongs to
this interval. Therefore, for any client $c\in C^{\prime}_{f}$,

$\displaystyle 0\leq h(c)=d(c,f)^{2}$
$\displaystyle\leq\left(\frac{1}{|C^{\prime}_{f}|}\sum_{c\in
C^{\prime}_{f}}d(c,f)+2R\right)^{2}$ $\displaystyle\leq
2\left(\frac{1}{|C^{\prime}_{f}|}\sum_{c\in
C^{\prime}_{f}}d(c,f)\right)^{2}+2\big{(}2R\big{)}^{2}$
$\displaystyle\leq\frac{2}{|C^{\prime}_{f}|}\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+8R^{2},$ (10)

where the last inequality follows from $\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}\geq|C^{\prime}_{f}|\big{(}\frac{1}{|C^{\prime}_{f}|}\sum_{c\in
C^{\prime}_{f}}d(c,f)\big{)}^{2}$, which is an application of Cauchy-Schwarz.

We define $M$ as the expression (10). Then, apply Lemma A.3 with remaining
assignments $U:=S^{\prime}_{f}$, $V:=C^{\prime}_{f}$, $\delta:=0.1\epsilon M$,
$\lambda:=n^{-20}$, which satisfy the requirements of the lemma. Following
(4), we can bound the flow in step (1) as

$\displaystyle h(S^{\prime}_{f})\cdot\frac{N}{r}$ $\displaystyle\leq
h(C^{\prime}_{f})\cdot\frac{|S^{\prime}_{f}|}{|C^{\prime}_{f}|}\cdot\frac{N}{r}+\delta|C^{\prime}_{f}|$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\text{Clm}\,\ref{clm:S-conc}}}}{{\leq}}h(C^{\prime}_{f})\cdot\frac{(1+0.1\epsilon)|C^{\prime}_{f}|\cdot
r/N}{|C^{\prime}_{f}|}\cdot\frac{N}{r}+\delta|C^{\prime}_{f}|$
$\displaystyle=(1+0.1\epsilon)\cdot h(C^{\prime}_{f})+\delta|C^{\prime}_{f}|$
$\displaystyle=(1+0.1\epsilon)\cdot
h(C^{\prime}_{f})+0.1\epsilon\left(\frac{2}{|C^{\prime}_{f}|}\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+8R^{2}\right)|C^{\prime}_{f}|$
$\displaystyle=(1+0.1\epsilon)\cdot h(C^{\prime}_{f})+0.2\epsilon\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+0.8\epsilon R^{2}|C_{f}|$
$\displaystyle=(1+0.3\epsilon)\sum_{c\in C^{\prime}_{f}}d(c,f)^{2}+0.8\epsilon
R^{2}|C_{f}|.$

#### Step (2) and oversampling.

In the $k$-means case, we cannot directly bound the cost through (5) and (6),
and need to split into two cases. First, if we under-sampled, then
$f^{\prime}$ is a source, so we still need to route $N-|S_{f}^{\prime}|\cdot
N/r$ flow from $f^{\prime}$ to $f$, which as cost

$\displaystyle\left(N-|S_{f}^{\prime}|\cdot\frac{N}{r}\right)\cdot
d(f^{\prime},f)$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq:means-1})}}{{\leq}}\left(N-|S_{f}^{\prime}|\cdot\frac{N}{r}\right)\cdot\left(\frac{2}{|C^{\prime}_{f}|}\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+8R^{2}\right)$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\text{Clm}\,\ref{clm:S-conc}}}}{{\leq}}\big{(}0.1\epsilon\cdot|C^{\prime}_{f}|\big{)}\cdot\left(\frac{2}{|C^{\prime}_{f}|}\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+8R^{2}\right)$ $\displaystyle=0.2\epsilon\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+0.8\epsilon|C^{\prime}_{f}|R^{2}.$

Otherwise, if we over-sampled, then we still need to route at most $N/r$ flow
from one client to $f$ (since $|S^{\prime}_{f}|=\lfloor|C^{\prime}_{f}|\cdot
N/r\rfloor$, not $|C^{\prime}_{f}|\cdot N/r$), as well as the remaining flow
from clients in $S_{f}\setminus S^{\prime}_{f}$ to $f^{\prime}$. The first can
easily be bounded by

$0.01\epsilon\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+0.01\epsilon|C^{\prime}_{f}|R^{2},$

and the second by

$\displaystyle\sum_{c\in S_{f}\setminus
S^{\prime}_{f}}d(c,f^{\prime})^{2}\cdot\frac{N}{r}$
$\displaystyle\leq|S_{f}\setminus S^{\prime}_{f}|\cdot R^{2}\cdot\frac{N}{r}$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq:2})}}{{\leq}}\left(0.11\epsilon\cdot|C^{\prime}_{f}|\cdot\frac{r}{N}\right)\cdot
R^{2}\cdot\frac{N}{r}$ $\displaystyle=0.11|C^{\prime}_{f}|R^{2}.$

Altogether, summing up the expression gives $(1+O(\epsilon))\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+0.8\epsilon|C^{\prime}_{f}|R^{2}$.

#### Case $\mathbb{E}[|S_{f}|]\leq 0.05\epsilon r/k$.

In this case, since the total demand is so small, we can be a lot looser. For
brevity, we only bound one of the flows and omit the rest. Namely, the cost to
route all flow in $S^{\prime}_{f}$ to $f^{\prime}$ is at most

$\displaystyle\sum_{c\in S^{\prime}_{f}}d(c,f^{\prime})\cdot\frac{N}{r}$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq:means-1})}}{{\leq}}|S^{\prime}_{f}|\cdot\left(\frac{2}{|C^{\prime}_{f}|}\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+8R^{2}\right)\cdot\frac{N}{r}$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\text{Clm}\,\ref{clm:S-conc-
small}}}}{{\leq}}\ \ \frac{0.06\epsilon
r}{k}\cdot\left(\frac{2}{|C^{\prime}_{f}|}\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+8R^{2}\right)\cdot\frac{N}{r}$
$\displaystyle=\frac{0.12\epsilon}{k}\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+\frac{0.48\epsilon NR^{2}}{k}.$

Adding up the costs, we get $(1+O(\epsilon))\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+O(\epsilon)R^{2}|C^{\prime}_{f}|$. Finally, summing
over all $f\in F$, we obtain a total cost of

$\displaystyle\sum_{f\in F}\left[(1+O(\epsilon))\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+O(\epsilon)R^{2}|C^{\prime}_{f}|\right]$
$\displaystyle=(1+O(\epsilon))\sum_{f\in F}\sum_{c\in
C^{\prime}_{f}}d(c,f)^{2}+O(\epsilon)NR^{2}.$

Now observe that $\sum_{f\in F}\sum_{c\in C^{\prime}_{f}}d(c,f)^{2}\leq OPT$,
since it describes part of the min-cost flow of
$\textup{{FlowInstance}}(\mathbbm{1})$, which has cost exactly $OPT$.
Therefore, the total error is at most $O(\epsilon)\cdot
OPT+O(\epsilon)NR^{2}$, proving Lemma C.1.

###  C.2 Multiple-rings case ($k$-means)

For the multiple-rings case, the arguments are identical, and we sum the error
in Lemma C.1 over each ring $C_{i,R}$. This totals

$\sum_{(i,R)}O(\epsilon)|C_{i,R}|R+\sum_{(i,R)}O(\epsilon)\cdot OPT\leq
O(\epsilon)\cdot OPT+O(k\log n)\cdot O(\epsilon)\cdot OPT.$

Recall that the core-set has size $O(k\log n/\epsilon^{3})$. To obtain error
$\epsilon\cdot OPT$, we need to reset
$\epsilon\leftarrow\Theta(\epsilon/(k\log n))$, so the total core-set size
becomes $O(k^{4}\log^{4}n/\epsilon^{3})$.

##  Appendix D Miscellaneous proofs

###  D.1 Proof of Theorem 2.7

We begin with a statement on a normalized version of Theorem 2.7:

######  Theorem D.1.

Let $x_{1},\ldots,x_{n}$ be independent random variables taking value $1$ with
probability $p$ and value $0$ with probability $1-p$, and let
$g:[0,1]^{n}\to\mathbb{R}$ be a $1$-Lipschitz function in $\ell_{1}$ norm.
Define $X:=(x_{1},\ldots,x_{n})$ and $\mu:=\mathbb{E}[g(X)]$. Then, for
$0\leq\epsilon\leq 1$:

$\Pr\big{[}\big{|}g(X)-\mathbb{E}[g(X)]\big{|}\geq\epsilon pn\big{]}\leq
2e^{-\epsilon^{2}pn/3}$

We follow Appendix A.1 of [AlS16], which proves the regular multiplicative
Chernoff bound, and adapt it for martingales.

Consider the following $n$-step martingale. We start off with the (constant)
random variable $\mathbb{E}[g(X)]$. On step $i\in[n]$, we reveal the choice of
$x_{i}$, and our random variable becomes $\mathbb{E}[g(X)]$ conditioned on the
outcomes of $x_{1},\ldots,x_{i}$, that is,
$\mathbb{E}\left[g(X)\big{|}x_{1},\ldots,x_{i}\right]$. Let
$\Delta_{i}:=\mathbb{E}\left[g(X)\big{|}x_{1},\ldots,x_{i}\right]-\mathbb{E}\left[g(X)\big{|}x_{1},\ldots,x_{i-1}\right]$
be the change in our random variable on step $i$. Therefore, our random
variable after step $i$ is $\mathbb{E}[g(X)]+(\Delta_{1}+\cdots+\Delta_{i})$,
and at the end of the process, our deviation from $\mathbb{E}[g(X)]$ is
exactly $\sum_{i=1}^{n}\Delta_{i}$. Therefore,

$\Pr[|g(X)-\mathbb{E}[g(X)]|\geq\epsilon
pn]=\Pr\big{[}\big{|}\textstyle\sum_{i=1}^{n}\Delta_{i}\big{|}\geq\epsilon
pn\big{]},$

so we focus on bounding $|\sum_{i}\Delta_{i}|$ instead.

Since $g$ is $1$-Lipschitz, a standard argument in martingale analysis says
that $\Delta_{i}\in[-1,1]$ with probability $1$. Furthermore, since
$\mathbb{E}[\Delta_{i}]=0$, there must exist $z_{i}\in[0,1]$ (depending on
$x_{1},\ldots,x_{i-1}$) such that $\Delta_{i}$ takes value $(1-p)z_{i}$ with
probability $p$ and $-pz_{i}$ with probability $1-p$. We now state the
following helper claim:

######  Claim 7.

Fix $z\in[0,1]$, and let $\Delta$ be a random variable that is $(1-p)z$ with
probability $p$ and $-pz$ with probability $1-p$. Then, for any
$\lambda\in\mathbb{R}$,

$\mathbb{E}\left[e^{-\lambda\Delta}\right]\leq e^{-\lambda
p}\left[pe^{\lambda}+(1-p)\right].$

######  Proof D.2.

We have

$\displaystyle\mathbb{E}\left[e^{-\lambda\Delta}\right]=pe^{\lambda(1-p)z}+(1-p)e^{-\lambda
pz}.$ (11)

We just need to show that this expression is maximized when $z=1$, so that
$\mathbb{E}[e^{-\lambda\Delta}]\leq pe^{\lambda(1-p)}+(1-p)e^{-\lambda
p}=e^{-\lambda p}[pe^{\lambda}+(1-p)]$. Differentiating (11) w.r.t. $z$, we
get $\lambda p(1-p)e^{-\lambda pz}[e^{\lambda}-1]$, which is nonnegative
because $\lambda[e^{\lambda}-1]\geq 0$ for all $\lambda$, finishing the proof.

We now proceed with bounding $|\sum_{i}\Delta_{i}|$, which follows Appendix
A.1 of [AlS16] and resembles the standard multiplicative Chernoff bound proof.
We bound $\Pr[\sum_{i}\Delta_{i}>a]$ as follows:

$\displaystyle\Pr[\textstyle\sum_{i}\Delta_{i}>a]$
$\displaystyle=\Pr[\exp(\lambda\textstyle\sum_{i}\Delta_{i})>\exp(\lambda a)]$
$\displaystyle<e^{-\lambda
a}\mathbb{E}[\exp(\lambda\textstyle\sum_{i}\Delta_{i})]$
$\displaystyle=e^{-\lambda
a}\displaystyle\prod\limits_{i}\mathbb{E}\left[e^{\lambda\Delta_{i}}\big{|}\Delta_{1},\ldots,\Delta_{i-1}\right]$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\text{Clm}\,\ref{clm:z}}}}{{\leq}}e^{-\lambda
a}\prod_{i}\left(e^{-\lambda p}\left[pe^{\lambda}+(1-p)\right]\right)$
$\displaystyle=e^{-\lambda a}e^{-\lambda
pn}\left[pe^{\lambda}+(1-p)\right]^{n}.$

Similarly, we bound $\Pr[\sum_{i}\Delta_{i}<-a]$ as follows:

$\displaystyle\Pr[\textstyle\sum_{i}\Delta_{i}<-a]$
$\displaystyle=\Pr[\exp(-\lambda\textstyle\sum_{i}\Delta_{i})>\exp(\lambda
a)]$ $\displaystyle<e^{-\lambda
a}\mathbb{E}[\exp(-\lambda\textstyle\sum_{i}\Delta_{i})]$
$\displaystyle=e^{-\lambda
a}\displaystyle\prod\limits_{i}\mathbb{E}\left[e^{-\lambda\Delta_{i}}\big{|}\Delta_{1},\ldots,\Delta_{i-1}\right]$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\text{Clm}\,\ref{clm:z}}}}{{\leq}}e^{-\lambda
a}\prod_{i}\left(e^{\lambda p}\left[pe^{-\lambda}+(1-p)\right]\right)$
$\displaystyle=e^{-\lambda a}e^{\lambda
pn}\left[pe^{-\lambda}+(1-p)\right]^{n},$

where the application of Claim 7 uses $-\lambda$ in place of $\lambda$ this
time around.

It remains to use approximations to simplify the expressions. Instead of
repeating them here, we refer the reader to the same approximations that
precede Corollary A.1.14 of Appendix A.1 of [AlS16]. We arrive at an analogous
statement to Corollary A.1.14 for martingales:

######  Claim 8.

$\Pr[|g(X)-\mathbb{E}[g(X)]>\epsilon pn]<2e^{-c_{\epsilon}pn}$, for
$c_{\epsilon}:=\min\\{-\ln(e^{\epsilon}(1+\epsilon)^{-(1+\epsilon)}),\epsilon^{2}/2\\}$.

Finally, it is easy to check that for all $\epsilon\in[0,1]$,
$-\ln(e^{\epsilon}(1+\epsilon)^{-(1+\epsilon)})\geq\epsilon^{2}/3$. Thus,
$c_{\epsilon}\geq\epsilon^{2}/3$, concluding Theorem D.1.

See 2.7

######  Proof D.3.

Define $X^{\prime}:=X/b=(x_{1}/b,x_{2}/b,\ldots,x_{n}/b)$, so that every
coordinate of $X^{\prime}$ is independently $1$ with probability $p$ and $0$
with probability $1-p$. Define $g^{\prime}(Y):=g(bY)$, which is
$bL$-Lipschitz, which means $g^{\prime}/(bL)$ is $1$-Lipschitz. Observe that
$g^{\prime}(X^{\prime})=g^{\prime}(X/b)=g(X)$, and

$\left|\frac{g^{\prime}(X^{\prime})}{bL}-\mathbb{E}\left[\frac{g^{\prime}(X^{\prime})}{bL}\right]\right|\geq\epsilon
pn\iff\big{|}g(X)-\mathbb{E}\big{[}g(X)\big{]}\big{|}\geq\epsilon pnbL.$

Therefore, it suffices to prove that

$\Pr\left[\left|\frac{g^{\prime}(X^{\prime})}{bL}-\mathbb{E}\left[\frac{g^{\prime}(X^{\prime})}{bL}\right]\right|\geq\epsilon
pn\right]\leq e^{-\epsilon^{2}pn/3}.$

This follows directly from Theorem D.1 on $X^{\prime}$ and $g^{\prime}/(bL)$,
as desired.

###  D.2 Proof of Claim 2

See 2

######  Proof D.4.

Let $k:=pN$ and $\ell:=N-k$. The probability can be approximated by Stirling’s
formula, as follows:

$\displaystyle\binom{N}{k}p^{k}(1-p)^{N-k}$
$\displaystyle=\frac{N!}{k!\ell!}p^{k}(1-p)^{\ell}$
$\displaystyle\sim\frac{(2\pi N)^{-1/2}(N/e)^{N}}{(2\pi
k)^{-1/2}(k/e)^{k}\cdot(2\pi\ell)^{-1/2}(\ell/e)^{\ell}}p^{k}(1-p)^{\ell}$
$\displaystyle=\left(\frac{N}{2\pi k\ell}\right)^{1/2}\cdot
N^{N}\left(\frac{p}{k}\right)^{k}\left(\frac{1-p}{\ell}\right)^{\ell}$
$\displaystyle=\left(\frac{N}{2\pi(pN)\ell}\right)^{1/2}\cdot
N^{N}\left(\frac{p}{pN}\right)^{k}\left(\frac{1-p}{N-pN}\right)^{\ell}$
$\displaystyle=\left(\frac{N}{2\pi(pN)\ell}\right)^{1/2}=\left(\frac{1}{2\pi
p\ell}\right)^{1/2}\geq\left(\frac{1}{2\pi N}\right)^{1/2},$

where the last inequality uses $p\leq 1$ and $\ell\leq N$.