# Deterministic Clustering in High Dimensional Spaces: Sketches and
Approximation

Vincent Cohen-Addad Google Research, France David Saulpic IST Austria. This
project has received funding from the European Union’s Horizon 2020 research
and innovation programme under the Marie Skłodowska-Curie grant agreement No
101034413 Chris Schwiegelshohn Aarhus University

###### Abstract

In all state-of-the-art sketching and coreset techniques for clustering, as
well as in the best known fixed-parameter tractable approximation algorithms,
randomness plays a key role. For the classic $k$-median and $k$-means
problems, there are no known deterministic dimensionality reduction procedure
or coreset construction that avoid an exponential dependency on the input
dimension $d$, the precision parameter $\varepsilon^{-1}$ or $k$. Furthermore,
there is no coreset construction that succeeds with probability $1-1/n$ and
whose size does not depend on the number of input points, $n$. This has led
researchers in the area to ask what is the power of randomness for clustering
sketches [Feldman WIREs Data Mining Knowl. Discov’20].

Similarly, the best approximation ratio achievable deterministically without a
complexity exponential in the dimension are $1+\sqrt{2}$ for $k$-median
[Cohen-Addad, Esfandiari, Mirrokni, Narayanan, STOC’22] and $6.12903$ for
$k$-means [Grandoni, Ostrovsky, Rabani, Schulman, Venkat, Inf. Process.
Lett.’22]. Those are the best results, even when allowing a complexity FPT in
the number of clusters $k$: this stands in sharp contrast with the
$(1+\varepsilon)$-approximation achievable in that case, when allowing
randomization.

In this paper, we provide deterministic sketches constructions for clustering,
whose size bounds are close to the best-known randomized ones. We show how to
compute a dimension reduction onto $\varepsilon^{-O(1)}\log k$ dimensions in
time $k^{O\left(\varepsilon^{-O(1)}+\log\log k\right)}\text{poly}(nd)$, and
how to build a coreset of size
$O\left(k^{2}\log^{3}k\varepsilon^{-O(1)}\right)$ in time
$2^{\varepsilon^{O(1)}k\log^{3}k}+k^{O\left(\varepsilon^{-O(1)}+\log\log
k\right)}\text{poly}(nd)$. In the case where $k$ is small, this answers an
open question of [Feldman WIDM’20] and [Munteanu and Schwiegelshohn,
Künstliche Intell. ’18] on whether it is possible to efficiently compute
coresets deterministically.

We also construct a deterministic algorithm for computing
$(1+\varepsilon)$-approximation to $k$-median and $k$-means in high
dimensional Euclidean spaces in time
$2^{k^{2}\log^{3}k/\varepsilon^{O(1)}}\text{poly}(nd)$, close to the best
randomized complexity of $2^{(k/\varepsilon)^{O(1)}}nd$ (see [Kumar,
Sabharwal, Sen, JACM 10] and [Bhattacharya, Jaiswal, Kumar, TCS’18]).

Furthermore, our new insights on sketches also yield a randomized coreset
construction that uses uniform sampling, that immediately improves over the
recent results of [Braverman et al. FOCS ’22] by a factor $k$.

##  1 Introduction

Clustering is the task of partitioning a dataset in a meaningful way such that
similar data elements are in the same part and dissimilar ones in different
parts. Clustering problems are among the most studied problems in theoretical
computer science. Clustering applications range from data analysis [JSB12] to
compression [Llo82], and this has given raise to several different ways of
modeling the problem. The $k$-median and $k$-means problems are among the most
prominent clustering objectives: algorithmic solutions to these problems are
now part of the basic data analysis toolbox, and used as subroutines for many
machine learning procedures [LW09, CNL11, CN12]. Furthermore, $k$-median and
$k$-means have deep connections with other classical optimization problems,
and understanding their complexity has been a fruitful research direction:
Their study has led to many interesting algorithmic development (for instance
for primal-dual algorithms [JV01, LS13, BPR+15] or local-search based ones
[CGH+22, CGLS23]).

Given a metric space $(X,\text{dist})$, and two sets $P,\mathbb{C}\subseteq
X$, the goal of the $k$-median problem (respectively $k$-means problem) is to
find a set of $k$ centers $\mathcal{S}\in\mathbb{C}^{k}$ in order to minimize
the sum of distances (resp. distances squared) for each point in $P$ to its
closest center in $\mathcal{S}$. The complexity of the $k$-median and
$k$-means problems, and the algorithmic techniques used to solve them, depends
naturally on the underlying metric space. Several works have thus focus on
Euclidean inputs that are arguably the most common case in practice, and
exhibits deep algorithmic challenges. Indeed, in that case the set of
candidate centers $\mathbb{C}$ is infinite, and even computing the solution to
$1$-median – also called the Fermat-Weber problem – is not easy: there is no
closed form formula, and many works investigated the complexity required to
approximate the best center [CT89, CMMP13, BHPI02, CLM+16].

Most of the algorithmic tools to handle the Euclidean version of $k$-median
and $k$-means are heavily reliant on randomization, and are Monte-Carlo
algorithms111A Monte-Carlo algorithm has a deterministic running time and a
fixed probability of success.: We do not know whether the algorithm succeeds
or not, hence, we cannot be sure of the result. This remark also holds for
sketching techniques for which it is unclear whether the sketch has the
desired properties.

We propose to study deterministic algorithms for clustering problems. This is
interesting from both practical and theoretical standpoints: from a practical
perspective, it makes sure that the results can be reproduced independently of
the underlying system or programming language222Obtaining similar
probabilistic outcomes over different architectures, computers, programming
languages is a challenge., and that they are correct; from a theoretical
standpoint, understanding the power of randomness in algorithms is a very
basic question and a recurring theme in theoretical computer science. We ask
in particular the following question:

######  Question 1.1.

Is it possible to deterministically compute $(1+\varepsilon)$-approximation
for $k$-median and $k$-means, in time competitive with the best randomized
result?

For high-dimensional Euclidean spaces, the best known algorithm has complexity
$2^{(k/\varepsilon)^{O(1)}}dn$ [KSS10]. In deterministic time however, only
constant-factor approximation are known, as for instance the primal-dual
algorithm of [ANSW20].

To tackle those clustering problems in high-dimensional spaces, one of the
most important tools is sketching, which has been a rich and vibrant area of
research for the past ten years. The efforts to design even smaller sketches
have resulted in an impressive success story producing algorithms with
performance guarantees, having high impact in practice [MJF19, MSSW18, LMFR21,
FVR16]. There are two natural ways of reducing the size of a $k$-median or
$k$-means input: First by computing a smaller set of points $B$ that
approximates the cost of any $k$-means (or $k$-median) solution of $A$. Such
sets are known as _coresets_. The second way consists in finding a projection
of the input point sets onto some low-dimensional space such that the
$k$-means (or $k$-median) cost of any partitioning is approximately preserved.
In this context, the quality of a sketch is usually quantified in terms of its
size, i.e.: the dependency on the size of the input $n$, the dimension $d$ of
the underlying Euclidean space (when there is one), the number of centers $k$,
and a precision parameter $\varepsilon$. For both objectives, we now have
optimal, or nearly optimal results, see [CSS21, CLSS22] for coresets
constructions and lower bounds and [MMR19, LN17] for dimension reduction.
These works are the results of a tremendous effort that has finally led to
dimensionality reduction and coreset bounds of size independent on $n$ (the
number of input points) and the dimension $d$ for the Euclidean case.

The applications for sketches go well beyond designing approximation
algorithms: they are at the heart of modern data analysis, allowing to process
efficiently big data and to design algorithms for models of computation where
the memory is constrained. For instance, they allow to design efficient
algorithms for the streaming model, distributed computing or massively-
parallel computations (MPC).

Interestingly – and somewhat frustratingly – these state-of-the-art results
are heavily reliant on randomization. Concretely, to achieve a success
probability of $1-\delta$, coreset constructions require
$\Omega_{k,\varepsilon}(\log(1/\delta))$ points, and dimension reduction
techniques require $\Omega_{k,\varepsilon}(\log(1/\delta))$-dimensional
spaces. Therefore, to construct a sketch (either a coreset or a dimension
reduction) that offers the desired guarantees with high probability (i.e.,
probability $1-\text{poly}(1/n)$ where $n$ is the original input size), the
dependency in $n$ strikes back. At the same time, randomized constructions
imply that there exist sketches whose size is independent on $n$. Therefore,
we ask:

######  Question 1.2.

Is it possible to deterministically construct $k$-median and $k$-means
sketches of size matching the best randomized results?

Finding deterministic coresets of small size is explicitly asked as an open
question in recent surveys on the coreset literature [Fel20, MS18].

The best deterministic constructions for Euclidean $k$-median yields coresets
of size $O(poly(k)\cdot\varepsilon^{-(d+O(1))})$ [HK07], which compares very
unfavourably to the best randomized result of size
$\tilde{O}(k\varepsilon^{-3})$ from [CLSS22]. In particular, it suffers from
the classic _curse of dimensionality_ and it is not clear a priori whether
such a dependency is needed when removing randomization. A notable exception
is for $k$-means, where it is possible to leverage the algebraic structure of
the problem to construct coresets of size
$k^{\varepsilon^{-2}\log(1/\varepsilon)}$ [FSS20]. Unfortunately, this
construction is very specific to $k$-means and does not apply to $k$-median,
and requires additional effort to be implemented deterministically.
Importantly, the construction yields a coreset whose size is very far from the
best known randomized bounds.

Suppose we were to relax the problem of deterministically computing a coreset
and aim for a Las-Vegas algorithm. 333Recall that a Las Vegas algorithm
returns a solution in expected polynomial time, whereas a Monte Carlo
algorithm only returns a solution with a small probability of failure. For
closely related problems such as locality sensitive hashing this is achievable
(see Ahle [Ahl17] and references therein). For clustering, all known
algorithms are Monte Carlo algorithms. The main barrier to obtaining a Las
Vegas algorithm (a challenging and interesting open problem as well) is that
we currently do not know how to verify that a candidate set of points is
indeed a valid coreset without evaluating all possible choices of $k$ centers
and verifying that the cost of each set of $k$ centers is preserved. This is
also a major roadblock for using conditional-expectation methods to
derandomize. For some tiny $\varepsilon$, the problem of verifying that a set
is a coreset is even co-NP-hard [SS22]. This stands in stark contrast with
other related techniques for which derandomization techniques have been
designed such as the Johnson Lindenstrauss lemma [EIO02], matrix approximation
[BDM11], or regression [Sar06].

###  1.1 Our Results

We phrase our results in terms of the $(k,z)$-clustering problems, a
generalization of both $k$-median and $k$-means: the cost function is
$\textsc{cost}(P,\mathcal{S})=\sum_{p\in
P}\min_{s\in\mathcal{S}}\text{dist}^{z}(p,s)$, and the goal is to find the
solution $\mathcal{S}$ that minimizes the cost. Thus, $z=1$ is the $k$-median
problem, $z=2$ is $k$-means.

Our main technical contribution lies in designing sketches to answer 1.2. We
start by showing a dimension reduction result:

######  Theorem 1.3 (Informal, see theorem 4.1).

Let $P$ be a set of $n$ points in $\mathds{R}^{d}$. We can compute in time
$k^{\varepsilon^{-O(z)}+\log\log k}\text{poly}(nd)$ a sketch of $P$ onto
$\varepsilon^{-O(z)}\cdot\log k$ dimensions that preserves the cost of any
$(k,z)$-clustering.

The optimal target dimension, even using randomization, is
$\Omega\left(\varepsilon^{-2}\log k\right)$: our result has therefore an
optimal dependency in $k$. The best known deterministic result was
$O\left(\varepsilon^{-2}\log n\right)$ (implicit in the work of [MMR19]), with
a dependency in $n$ that we precisely want to avoid.

Building on this dimension reduction result, we show how to construct coresets
deterministically:

######  Theorem 1.4 (Informal, see 5.3).

Let $P$ be a set of $n$ points in $\mathds{R}^{d}$. We can compute in time
$2^{\varepsilon^{-O(z)}k\cdot\log^{3}k}+k^{\varepsilon^{-O(z)}+\log\log
k}\text{poly}(nd)$ a set $\Omega\subset\mathds{R}^{d+1}$ of size
$O\left(k^{2}\log^{2}k\varepsilon^{-O(z)}\right)$ such that, for any set of
$k$ centers $\mathcal{S}\subset\mathds{R}^{d}$,

$\textsc{cost}(\Omega,\mathcal{S}^{\prime})=(1\pm\varepsilon)\textsc{cost}(P,\mathcal{S}),$

where $\mathcal{S}^{\prime}:=\left\\{\begin{pmatrix}s\\\
0\end{pmatrix},s\in\mathcal{S}\right\\}$ is the set $\mathcal{S}$ where we
append a 0 coordinate at each center.

This notion of coreset is used in [SW18], and is more general than the most
standard one (for which $\Omega\subset P$). However, it maintains the most
interesting property that any $\alpha$-approximation for $\Omega$ with all
last coordinate equal to zero is an $(1+\varepsilon)\alpha$-approximation for
$P$. Therefore, any good solution on $\Omega$ yields a good solution for $P$,
and we can compute that way a $(1+\varepsilon)$-approximation.

Those sketches directly imply deterministic streaming algorithm for
$(k,z)$-clustering, using the merge-and-reduce technique. The required memory
is merely $O\left(k^{2}d\log^{O(z)}n\varepsilon^{-O(z)}\right)$, where the
best randomized result requires memory
$O\left(kd\log^{2}n\varepsilon^{-O(z)}\right)$ to compute a
$(1+\varepsilon)$-approximation [BFLR19]. This also apply to distributed
computing and MPC models, matching the best randomized result up to
$\text{poly}(\log n,\varepsilon^{-1})$ factors.

In case $k$ is large (namely $\log k\log\log k\geq\log n$), we could replace
the complexity by $n^{O\left(\varepsilon^{-2}\right)}$. However, one
application of the sketches is to answer positively 1.1, for which having a
complexity in terms of $k$ is more desirable. We show:

######  Theorem 1.5.

For any fixed $z\geq 1,\varepsilon>0$, there exists a deterministic algorithm
that, given a set $P$ of $n$ points in $\mathds{R}^{d}$, computes a
$(1+\varepsilon)$-approximation to $(k,z)$-clustering on $P$ in time
$k^{\log\log
k+\varepsilon^{-O(z)}}\cdot\text{poly}(nd)+2^{k\log^{3}k\cdot\varepsilon^{-O(z)}}$.

Guruswamy and Indyk [GI03] showed it is NP-hard to compute an approximation
arbitrarily close to $1$ in dimension $O(\log n)$ (and for arbitrary $k$):
hence, to have a polynomial running time in the dimension, an exponential
dependency in $k$ is necessary. Our theorem essentially matches the best
randomized running time of [KSS10] for $k$-median and $k$-means, of
$2^{(k/\varepsilon)^{O(1)}}nd$.

###  1.2 Implication of our work when allowing randomization.

We believe that the sketches we develop have interest beyond computing a
$(1+\varepsilon)$-approximation. Indeed, we develop new sketching techniques,
that improve over the best known bounds for some regime of parameters, and
that are of independent interest.

We remark that, if allowing randomization, our new sketch constructions can be
implemented faster and provide useful alternatives to the existing ones. For
dimension reduction, the randomized running time of our procedure is the one
to compute a Johnson-Lindenstrauss (JL) transform, in general $\tilde{O}(nd)$.
However, we can use _any_ JL transform to get our result, including the sparse
transforms (e.g., [KN14]) that allow for further speed-ups. This stands in
contrast with the [MMR19] result, which needs a particular additional property
on the JL transform they use, namely sub-gaussian tails, and therefore cannot
use the fastest JL embeddings.

More importantly, our coreset construction can be implemented using only
uniform sampling. The importance of uniform sampling was illustrated in the
recent paper [BCJ+22], as it gives an easier way of constructing coreset. Our
construction improves the one of [BCJ+22] by a factor $k$: if one can compute
a coreset of size $T$ for any _ring_
$P\subset\left\\{x:\|x\|\in[1/2,1]\right\\}$, then for any input one can
compute a coreset of size $O\left(T\cdot
k\log(1/\varepsilon)/\varepsilon\right)$ – as opposed to
$O\left(Tk^{2}/\varepsilon\right)$ in [BCJ+22].

This apply to any metric where the VC-dimension of the uniform function space
can be bounded, including shortest-path metric of minor-free graphs and
Fréchet distance.

###  1.3 Our Techniques

Given a coreset for $(k,z)$-clustering, it is quite straightforward to compute
a $(1+\varepsilon)$-approximation: one can simply enumerate all partitions of
the coreset into $k$ parts, evaluate their cost and keep the best partition.
The running time is thus $\min(k^{\text{coreset-size}},\text{corest-
size}^{kd})$, where the latter bound can be obtained through the result of
[IKI94].

Therefore, we focus on the construction of a coreset. For that, we first
require a dimension reduction tool, that we explain first.

####  1.3.1 Dimension Reduction

##### High-level overview.

There currently exist only two known methods that enable deterministic
dimension reduction. The first is principal component analysis and its
generalizations to other norms. Applying principal component analysis to
$k$-means requires a target dimension of $\Omega(k)$ in order to preserve the
$k$-means cost of each partition [CEM+15] up to a constant factor and thus
this attempt falls short of the $O(\log k)$ dimension we are aiming for.

The only known alternative is the conditional expectation method for
derandomizing Johnson Lindenstrauss transforms by Engebretsen, Indyk and
O’Donnell [EIO02]. At a high level, this method selects random bits of the
projection one by one, and selects the value of the next bit so as to minimize
the number of “bad events”, namely the number of vectors whose lengths are
distorted by a too high factor, conditioned on the bit’s value.

When applying this idea naively to a candidate embedding for $k$-clustering,
the number of “bad events” becomes the number of clusterings for which the
cost is not preserved. As there exist $n^{dk}$ many distinct clusterings
([IKI94]), this is infeasible in time polynomial in $n,d,k$. Thus, our goal is
to reduce the number of bad events necessary to count, in order to use the
conditional expectation method.

For this, our first contribution is to reduce the number of distinct
clusterings we need to test for. More precisely, we show that for any cluster,
a $(1+\varepsilon)$ approximate center lies in the convex hull of a subset of
the cluster of size $O\left(\varepsilon^{-2}\right)$, that we call a witness
set. Using a careful discretization argument, we can show that it is possible
to enumerate over all candidate solutions in the convex hulls of such witness
sets and thereby also to enumerate over all possible centers induced by any
clustering. This reduces the clustering problem with arbitrary centers in
$\mathds{R}^{d}$ to a discrete one, where centers are restricted to a finite
set, and it is therefore enough to preserve the distances from input points to
the discrete set of centers. There are $n^{O\left(\varepsilon^{-2}\right)}$
many possible witness sets – any set of $O\left(\varepsilon^{-2}\right)$ input
points. Hence, counting the “bad events” now requires to test
$n^{O\left(\varepsilon^{-2}\right)}$ many clusterings. This is still
infeasible in our target running time, but, crucially, does not depend in the
dimension $d$ anymore.

To improve further, the idea is to reduce the number of distinct points to
$\text{poly}(k,\varepsilon^{-1})$, in order to reduce the number of possible
witness sets. A coreset is the most natural idea here. However the typical
guarantees of coresets are not strong enough for our purposes: as explained in
section 2, coresets preserve the cost to any set of $k$ centers, while our
goal here is to preserve the cost of any partition. In turn, we naturally
introduce the notion of partition coreset, which are small sets preserving the
cost of any partition. We show how to construct deterministically partition
coresets of size $k^{\varepsilon^{-O(z)}}$; hence, using the witness sets of
this partition coreset, we are able to limit the number of clusterings to
$k^{O\left(\varepsilon^{-2}\right)}$. We can therefore list all the potential
bad events and count their number, and reduce the dimension to
$\varepsilon^{-O(z)}\log k$ – log of the number of distances to be preserved.
We point that the notion of partition coreset, more general then the usual
coreset definition, may be of independent interest and have further
application in the future.

##### Construction of partition coreset.

To build a partition coreset, a first attempt would be to use a $k^{\prime}$
clustering such that its cost is at most an $\varepsilon$-fraction of the cost
of an optimal $k$-clustering. In that case, the cost of snapping each input
point to its closest center would be negligible, and the cost of any partition
would be preserved. Unfortunately, such a set has size at least
$\varepsilon^{-d}$ in the worst case. Instead, we show – and this is our main
technical contribution – that there exists a $k^{\prime}$ clustering such that
for each cluster, either the cluster is very cheap, or its cost cannot
decrease by adding additional centers. We show such a statement for
$k^{\prime}=k^{\varepsilon^{-O(z)}}$. The guarantee we ask on the $k^{\prime}$
clustering is somewhat non-standard, as the cost in each cluster should not
decrease by adding $k$ centers (as opposed to the global cost). In the first
case, the set of centers directly gives a partition coreset. The second case
implies essentially that the points in some cluster of the $k^{\prime}$
clustering pay the same cost in any possible $k$-clustering. Hence, we can
simply replace those points by their center, and encode the cost difference in
an extension coordinate.

To illustrate further our argument, suppose that we are given a center $m$
such that the cost of clustering to $m$ is nearly the same as clustering to
the optimum $k$ centers. Then, we show that in _any_ clustering into $k$ parts
with centers $c_{1},...,c_{k}$, for almost all points $p$ of $c_{i}$’s
cluster, one of the following condition is verified:

  * •

either $p$ is really close to $m$ compared to $c_{i}$, namely
$\|p-m\|\leq\varepsilon\|m-c_{i}\|$,

  * •

or $c_{i}$ is really close to $m$ compared to $p$,
$\|m-c_{i}\|\leq\varepsilon\|p-m\|$

  * •

or the segment between $p$ and $m$ is nearly orthogonal to the one between $m$
and $c_{i}$.

Each of those conditions implies that
$\|p-c_{i}\|\approx\left(\|m-c_{i}\|^{2}+\|p-m\|^{2}\right)^{1/2}$: we can
therefore replace the point $p$ by $f(p)\in\mathds{R}^{d+1}$, where the first
$d$ coordinates are the ones of $m$ and the _extension coordinate_ is
$\|p-m\|$. Now, for any possible center $c_{i}$, the distance from $p$ to
$c_{i}$ is roughly the one from $f(p)$ to $\begin{pmatrix}c_{i}\\\
0\end{pmatrix}$ ($c_{i}$ with an extension coordinate $0$). Therefore, the
cost of clustering to $\\{c_{1},...,c_{k}\\}$ before the transformation is the
same as clustering to $\left\\{\begin{pmatrix}c_{1}\\\
0\end{pmatrix},...,\begin{pmatrix}c_{k}\\\ 0\end{pmatrix}\right\\}$ after the
transformation. Furthermore, after transformation, all points have the same
first $d$ coordinates (equal to $m$), and all centers are required to have
last coordinate zero. Therefore, we have a small partition coreset for those
points satisfying one of the condition.

We deal separately with points satisfying none of them. Using the fact that
the cost of clustering to $m$ is nearly the same as to clustering to $k$
centers, we can show that those points have a very tiny cost to $m$, and are
easier to deal with.

Applying that construction to all clusters of the $k^{\prime}$ clustering
whose cost do not decrease by adding $k$ centers, we get a set of points in
$\mathds{R}^{d+1}$ where the first $d$ coordinates are one of the $k^{\prime}$
centers. From this, we manage to build a set of candidate centers capturing
all clustering, of size $k^{\prime O(\varepsilon^{-2})}$ – henceforth
independent of $n$. This concludes our algorithm: To reduce the dimension and
preserve the cost of all clustering, it is enough to preserve distances
between points of the partition coreset and the discrete set of centers, i.e.,
between $k^{\varepsilon^{-O(z)}}$ many points, which can be done using a
derandomized Johnson-Lindenstrauss projection.

The last missing piece to the argument is to compute effectively this
$k^{\prime}$ clustering deterministically. This is not straightforward either,
as it requires to compute a $(1+\varepsilon)$-approximation to
$(k,z)$-clustering. The standard techniques to do so rely on dimension
reduction: using ours leads to a loop in the argument. Instead, we use another
JL construction (specifically, the one of Kane and Nelson [KN14]) that
requires few random bits. Enumerating over all possible random bits provides a
a (somewhat) small set of projections, such that at least one is a good
dimension reduction for clustering. For each of the projections, we can
compute a $(1+\varepsilon)$-approximate solution in the projected space, and
then lift it back to the original $\mathds{R}^{d}$. For the projections that
do not preserve the cost, those solutions in $\mathds{R}^{d}$ may be bad:
however, for the good projection, this solution will be a
$(1+\varepsilon)$-approximation in the original metric as well. Enumerating
over all possible solutions computed that way allows therefore to compute a
$(1+\varepsilon)$-approximation. It is then possible to use this algorithm to
compute the desired $k^{\prime}$ clustering, which concludes our whole
algorithm.

####  1.3.2 Coresets

We show a generic coreset construction, based on a careful preprocessing of
the input and VC-dimension techniques. This can be applied to the Euclidean
space, using our partition coresets and dimension reduction, to obtain even
smaller coresets.

Building on the work of Chen [Che09], we show that constructing a coreset
reduces to sampling uniformly. For this, we essentially compute a bi-criteria
approximation and partition points in exponential rings according to their
cost in the bi-criteria. There are $O(k\log n)$ rings, and Chen showed that
uniform sampling among them yield a coreset. Our key new ingredient here is to
show how to go from $O(k\log n)$ to only $O(k)$ rings. For this, our key
contribution is to start from a structured bi-criteria approximation, in the
same spirit as what we did for the partition coreset. In particular, we ensure
that the cost of that solution cannot decrease by adding $k$ more centers. We
infer from that property that the cost of the points “far” from the bi-
criteria centers cannot be much different in any solution. We show that we can
replace them by copies of the center, and encode their cost in an additive
offset $F$. This structural observation introduces a clean and elegant way of
removing the dependency in $n$ from the coreset size. Similarly to what is
done in [CSS21] (although their techniques are deeply randomized), this
informally hints that the “far” points do not affect clustering algorithms.

Next, we observe that instead of sampling points in each ring, it is enough to
build an $\varepsilon$-approximation of a particular set system, formed by $k$
balls. It is well known that the VC-dimension of that set system is bounded by
$O(kd\log k)$ in Euclidean space of dimension $d$: hence, using a standard
algorithm, this leads to $\varepsilon$-approximation of size
$\tilde{O}(\frac{kd\log k}{\varepsilon^{2}})$.

Unfortunately, the running time of these constructions is exponential in the
VC dimension, which is $k\cdot d\log k$ in our case. To eliminate the
dependency on $d$, we apply first our construction of partition coreset: this
reduces the size of the input to $k^{\varepsilon^{-O(z)}}$. We can then embed
the input into a low dimensional space via terminal embeddings. Terminal
embeddings are commonly used as a coreset preserving dimension reduction, see
[BBC+19, BJKW21, CSS21, HV20] and the construction by Mahabadi, Makarychev,
Makarychev and Razenshteyn [MMMR18] can be made deterministic. That way, we
are able to obtain coresets of size $O(k^{2}\cdot\varepsilon^{-O(1)})$ in time
$n^{O(\varepsilon^{-2}\log
1/\varepsilon)}+exp(\text{poly}(k,\varepsilon^{-1}))$.

###  1.4 Related Work

##### Approximation of $(k,z)$-clustering

In general discrete metric spaces, $k$-median is NP-hard to approximate better
than $1+2/e$, and $k$-means better than $1+8/e$. Those two bounds can be
obtained by FPT algorithms running in time $f(k,\varepsilon)\text{poly}(n)$
[CGK+19]. In polynomial time, the best approximation for $k$-median has been
very recently improved to $2.613$ [CGLS23, GPST23], and $6.1290$ for $k$-means
[GOR+22].

In Euclidean spaces, the picture is quite different as there are infinitely
many possible centers location. The problems are NP-hard even for $d=2$ or
$k=2$. The best approximation ratio are $2.406$ for $k$-median and $5.912$ for
$k$-means, in polynomial time [CEMN22].

However, it is possible to compute $(1+\varepsilon)$-approximations: either in
time $f(\varepsilon,d)n\text{polylog}(n)$ [CFS21] or in time
$2^{(k/\varepsilon)^{O(1)}}nd$ by [KSS10]. We show how to match the latter
running time, deterministically.

##### Coresets

The introduction essentially covered the most important deterministic coreset
constructions. The state-of-the art for $k$-median an $k$-means is a size
$O(k^{3}\cdot\varepsilon^{-d-1})$ [HK07], or $O(k\cdot\varepsilon^{-d-1}\log
n)$ [HM04]. Other examples for deterministic constructions can be found in
[BJKW19, FGS+13, FS05, HJV19]. These and the aforementioned algorithms were
only claimed for $k$-median and $k$-means, but in our view could easily be
extended to arbitrary powers (with the exception of the
$k^{O(\varepsilon^{-2}\log 1/\varepsilon)}$ size coreset for $k$-means by
[FSS20]). The literature on sampling based coreset algorithms for clustering
is vast, see [FL11, FSS13, HV20, SW18, CSS21, CLS+22, Che09, HJLW18] and
references therein. As for lower bounds, any coreset for $k$-means and
$k$-median in Euclidean space must have size
$\Omega\left(k\varepsilon^{-2}\right)$ [CLSS22].

Other notable problems for which we have deterministic coresets include extent
approximation problems [AHV04, Cha04], the minimum enclosing ball problem
[BC03, BHI02], determinant maximization [IMGR20, MIGR19], page rank[LBS+19],
diversity [CPP20, IMMM14], subspace approximation [FSS13], and spectral
sparsification [BSS09].

##### Dimension Reduction

Most dimension reduction efforts have been on the $k$-means problem. A long
line of research has studied the relationship between $k$-means and principal
component analysis / singular value decomposition, see [BM13, DFK+04, FSS13]
and most notably Cohen, Elder, Musco, Musco and Persu [CEM+15], who showed
that projecting onto the subspace spanned by the first $\lceil
k/\varepsilon\rceil$ principal components approximates the cost of any
clustering up to a $(1+\varepsilon)$-factor and that this bound is tight.

The alternative to PCA-based algorithms are random projections and terminal
embeddings. For the former, [EIO02] proposed a derandomization scheme with
target dimension $O(\varepsilon^{-2}\log n)$, where $n$ is the number of
vectors to be preserved. For terminal embeddings, the algorithm proposed by
Mahabadi, Makarychev, Makarychev and Razenshteyn [MMMR18] achieves a target
dimension of $O(\varepsilon^{-4}\log n)$ and is deterministic. The guarantee
of a terminal embedding is somewhat stronger than that of [EIO02]: given a
fixed set of points $X\in\mathbb{R}^{d}$, a terminal embedding is a mapping of
$\mathbb{R}^{d}$ to $\mathbb{R}^{m}$ such that for any $y\in\mathbb{R}^{d}$
and any $x\in X$, the pairwise distance between $y$ and $x$ is preserved. At
the same time, terminal embeddings are not linear, which can be a drawback.
Other highly related deterministic algorithms exist for neareset neighbor
search in high dimension, see [AAKK14, Ben75, CGL04, HIM12, Ind03] and
references therein, as well as sparse recovery [IP11, LN20, NNW12].

The literature for randomized algorithms is vast, see [BBC+19, CEM+15, EFN17,
FKW19, KR15, NN19, SW18], and most notably the recent and nearly optimal
result by Makarychev, Makarychev and Razenshteyn [MMR19] for works with
special bearing on $k$-clustering.

###  1.5 Roadmap

After introducing useful definitions and result in section 2, we present our
construction of partition coreset in section 3. We first apply it to construct
a deterministic dimension reduction in section 4, and then combine the results
to construct small coresets in section 5. Finally, we present in section 6 the
bicriteria approximation algorithm, used as a building block in the previous
parts.

##  2 Preliminaries

###  2.1 Notations

We use $a=(1\pm\varepsilon)b$ as an abbreviation for $(1-\varepsilon)b\leq
a\leq(1+\varepsilon)b$. For a $d$-dimensional vector $x$, we define the
$\ell_{z}$ norm $\|x\|_{z}=\sqrt[z]{\sum_{i=1}^{d}|x_{i}|^{z}}$. In Euclidean
spaces, we let $\text{dist}(\cdot,\cdot)$ denote the $\ell_{2}$ distance.

Given a metric space $(X,\text{dist})$, a set of points $P\subset X$ and
$\mathcal{S}\subset X$, we define $\textsc{cost}^{z}(P,\mathcal{S})=\sum_{p\in
P}\min_{s\in\mathcal{S}}\text{dist}(p,s)^{z}$. The $(k,z)$-clustering
objective consists of finding a set of at most $k$ centers $\mathcal{S}$ that
minimize $\textsc{cost}^{z}(P,\mathcal{S})$. For simplicity, we often drop the
$z$ and simply write $\textsc{cost}(P,\mathcal{S})$.

Another view on the problem is to find clusters rather than centers. Given a
set of points $P\subset X$, we define
$\mu^{z}(P):=\operatorname*{arg\,min}_{s}\textsc{cost}(P,\\{s\\})$ to be the
optimal center for $(1,z)$-clustering on $P$. For any partition
$\mathcal{C}=\\{C_{1},C_{2},...\\}$ of $P$, we define
$\textsc{P-cost}^{z}(P,\mathcal{C}):=\sum_{C\in\mathcal{C}}\textsc{cost}(C,\mu^{z}(C))$.

In Euclidean spaces, we say a set $P^{\prime}\subset\mathds{R}^{d+1}$ is an
extension of a multiset $P\subset\mathds{R}^{d}$ if for all $p\in P$, there
exists $p^{\prime}\in\mathds{R}$ such that
$P^{\prime}=\left\\{\begin{pmatrix}p\\\
p^{\prime}\end{pmatrix},p\in\right\\}$. The number $p^{\prime}$ is called the
extension of $p$. If all extensions are $0$, then $P^{\prime}$ is the
$0$-extension of $P$.

Finally, for any function $f$ that maps points of $X$ to some other metric, we
will abusively write $f(P):=\left\\{f(p):p\in P\right\\}$, and for a partition
$\mathcal{C}$, $f(\mathcal{C})$ is the partition
$\left\\{f(C_{1}),f(C_{2}),...\right\\}$.

When clustering extensions, we will enforce centers to have extension
coordinate $0$. Therefore, for a set of points $X\subset\mathds{R}^{d+1}$, we
define
$\mu^{z}_{0}(X):=\operatorname*{arg\,min}_{\begin{subarray}{c}s\in\mathbb{R}^{d+1}\\\
s_{d+1}=0\end{subarray}}\textsc{cost}^{z}(X,\\{s\\})$ to be the optimal center
for $(1,z)$-clustering on $P$ with the constraint that the extension
coordinate is $0$, and
$\textsc{P-cost}_{0}(P,\mathcal{C})=\sum_{C\in\mathcal{C}}\textsc{cost}^{z}(C,\mu^{z}_{0}(C))$.

###  2.2 Definitions

We can now define the dimension reduction guarantee we aim to satisfy.

######  Definition 2.1 (Cost Preserving Sketches for Powers).

Let $z$ be a positive integer and $\varepsilon>0$ a precision parameter. Let
$P\subset\mathds{R}^{d}$, and $f:\mathds{R}^{d}\rightarrow\mathds{R}^{m+1}$.

Then we say that $f$ is an $(k,z,\varepsilon)$-cost preserving sketch for $P$
if for every partition $\mathcal{C}$ of $P$ into $k$ sets,

$\textsc{P-cost}_{0}^{z}(f(P),f(\mathcal{C}))=(1\pm\varepsilon)\textsc{P-cost}^{z}(P,\mathcal{C}).$

This definition captures the guarantee satisfied for $(k,z)$-clustering given
by [MMR19], with the generalization of allowing $f(P)$ to have an extension.
Let us briefly compare this definition to cost preserving sketches for
$k$-means, defined as follows:

######  Definition 2.2 (Cost Preserving Sketches for $k$-means [CEM+15]).

Let $\varepsilon>0$ be a precision parameter. Let $P\subset\mathds{R}^{d}$,
and $f:\mathds{R}^{d}\rightarrow\mathds{R}^{m}$.

Then we say that $f$ is an $(k,2,\varepsilon)$-cost preserving sketch for $P$
if for every partition $\mathcal{C}$ of $P$ into $k$ sets,

$\textsc{P-cost}^{2}(f(P),f(\mathcal{C}))+F=(1\pm\varepsilon)\textsc{P-cost}^{2}(P,\mathcal{C}).$

It turns out that those two definitions are equivalent for the case $z=2$: the
offset $F$ used for $k$-means is a special case of adding extensions to $f(P)$
and requiring the extension coordinate of the centers being set to 0 (i.e.
$s_{m+1}=0$). Writing $f(p)=\begin{pmatrix}f^{\prime}(P)\\\
p^{\prime}\end{pmatrix}$ and $\mu_{0}^{z}(C)=\begin{pmatrix}\mu_{C}\\\
0\end{pmatrix}$ we indeed have for $z=2$

$\sum_{C\in\mathcal{C}}\sum_{p\in
C}\|f(p)-\mu_{0}^{z}(C)\|^{2}=\sum_{C\in\mathcal{C}}\sum_{p\in
C}\text{dist}(f^{\prime}(p),\mu_{C})^{2}+{p^{\prime}}^{2}.$

Note that the contribution of the final coordinate is independent of the
choice of centers, under the constraint $c_{m+1}=0$. Hence, the offset $F$ is
equivalent to $\sum_{p\in P}{p^{\prime}}^{2}$. Second, $\mu_{C}$ is exactly
the mean of $C$, regardless of the extension coordinates: hence,
$\textsc{P-cost}^{2}(f(P),f(\mathcal{C}))+F=\textsc{P-cost}_{0}^{2}(f^{\prime}(P),f^{\prime}(\mathcal{C}))+\sum_{p\in
P}P^{\prime}$, and the two definitions coincides.

In order to construct our cost preserving sketches, we will rely on partition
coreset, defined as follows:

######  Definition 2.3 (Partition Coresets (see [SW18])).

Let $B$ be a multiset consisting of several copies of points in
$\mathds{R}^{d}$, with total size $|P|$.

$B$ is an $(\varepsilon,k,z)$-extension partition coreset of $P$ if there
exists an extension $B^{\prime}$ of $B$ and a one-to-one mapping
$g:P\rightarrow B^{\prime}$ such that for any partition
$\mathcal{C}=\\{C_{1},...,C_{k}\\}$ into $k$ parts and any centers
$\mathcal{S}=\\{s_{1},...,s_{k}\\}$ with $0$-extension
$\\{s^{\prime}_{1},...,s^{\prime}_{k}\\}$, it holds that

$\sum_{i=1}^{k}\sum_{p\in
C_{i}}\text{dist}(g(p),s^{\prime}_{i})^{z}=(1\pm\varepsilon)\sum_{i=1}^{k}\sum_{p\in
C_{i}}\text{dist}(p,s_{i})^{z}$

We say that the size of the coreset is the number of distinct points of $B$.

We insist on the fact that the size of an extension partition coreset is the
number of distinct points in $B$, not on the extension $B^{\prime}$.

This definition of coreset is somewhat stronger than the commonly found
definition that requires the cost of an assignment $\sum_{p\in
A}\underset{s\in\mathcal{S}}{\min}\text{dist}(p,s)^{z}$ to be approximated for
any set of $k$-centers $\mathcal{S}$. In our definition, the points are not
necessarily assigned optimally to the center set. This difference is crucial
for dimension reduction purposes, as guarantees required for cost preserving
sketches are related to partitions as well.

Coresets with extensions where introduced by Sohler and Woodruff [SW18] for
$k$-median only: our definition extends theirs, while providing a stronger
guarantee, as cost is preserved for any assignments and not only assignments
to the closest center.

Finally, we define the more standard coreset that we will work with in section
5. The definition of coreset we consider here allows for an _offset_ ,
originally due to Feldman, Schmidt and Sohler [FSS13]. For other works using
this definition, see [BBC+19, CEM+15, SW18, CSS21, CLSS22].

######  Definition 2.4.

Let $(X,\text{dist})$ be a metric space, and $P\subset X$. An
$(\varepsilon,k,z)$-coreset for the $(k,z)$-Clustering problem on $P$ is a set
$\Omega\subset X$ with weights $w:\Omega\rightarrow\mathds{R}_{+}$ together
with a scalar $F$ such that, for any set $\mathcal{S}\subset X^{d}$,
$|\mathcal{S}|=k$,

$\textsc{cost}^{z}(\Omega,\mathcal{S})+F=(1\pm\varepsilon)\textsc{cost}^{z}(P,\mathcal{S})$

As opposed to the previous sketches, those coresets preserve the cost of any
set of centers, instead of preserving the cost of any clustering. In
particular, those centers may not be the optimal ones for the induced
partition.

Lastly, a $(\alpha,\beta)$ bicriteria algorithm for clustering produces a
clustering with $\beta\cdot k$ centers and cost $\alpha\cdot OPT$, where $OPT$
denotes the cost of an optimal clustering with $k$ centers.

###  2.3 Useful Results

######  Lemma 2.5 (Triangle Inequality for Powers).

Let $a,b,c$ be an arbitrary set of points in a metric space with distance
function $d$ and let $z$ be a positive integer. Then for any $\varepsilon>0$

$d(a,b)^{z}\leq(1+\varepsilon)^{z-1}d(a,c)^{z}+\left(\frac{1+\varepsilon}{\varepsilon}\right)^{z-1}d(b,c)^{z}$

and

$\left|d(a,b)^{z}-d(a,c)^{z}\right|\leq\varepsilon\cdot
d(a,c)^{z}+\left(\frac{z+\varepsilon}{\varepsilon}\right)^{z-1}d(b,c)^{z}.$

Proofs of this inequality (and variants thereof) can be found in [BBC+19,
CS17, FSS13, MMR19])

We will use an algorithm that compute an approximation to $(k,z)$-clustering
up to a tiny error, as stated in the following theorem. We prove the theorem
in section 6: although key to our algorithms, the techniques to build this
approximation are distinct from our main techniques and we deferred the proof
to the end.

######  Theorem 2.6.

There exists an algorithm running in time $k^{\log\log
k+\log(1/\varepsilon)}\cdot\text{poly}(nd)$ that compute a set of
$O(k\cdot\log(1/\varepsilon)/\varepsilon)$ many centers $\mathcal{S}$, such
that
$\textsc{cost}(P,\mathcal{S})\leq(1+\varepsilon)\textsc{cost}(P,\text{OPT})$,
where OPT is the best solution with $k$ centers.

##### Derandomizing Random Projections.

The seminal Johnson-Lindenstrauss lemma states that any $n$ point set in
$d$-dimensional Euclidean space can be (linearly) embedded into a $m\in
O(\varepsilon^{-2}\log n)$ dimensional space such that all pairwise distances
are preserved up to a $(1\pm\varepsilon)$ factor. Most proofs show this
guarantee by sampling a matrix from an appropriate distribution. We will use
the following derandomization based on the conditional expectation method.

######  Theorem 2.7 ([EIO02]).

Let $v_{1},\ldots v_{n}$ be a sequence of vectors in $\mathbb{R}^{d}$ and let
$\varepsilon,F\in(0,1]$. Then we can compute in deterministic time $O(nd(\log
n\varepsilon^{-1})^{O(1)})$ a linear mapping
$S:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}$ where $m\in O(\varepsilon^{-2}\log
1/F)$ such that

$(1-\varepsilon)\cdot\|v_{i}\|_{2}\leq\|Sv_{i}\|_{2}\leq(1+\varepsilon)\|v_{i}\|_{2}$

for at least a $(1-F)$ fraction of the $i$’s.

Note that setting $F<1/n$ implies that the guarantee holds for all vectors.
Also, we note that if we are given $n$ points rather than $n$ vectors and wish
to preserve the pairwise distances, the running time has a quadratic
dependency on $n$ as there are ${n\choose 2}$ many distance vectors. Since the
running time is dominated by computing a bicriteria approximation, we will
omit it from the statement of our theorems.

##  3 Deterministic Partition Coresets for $(k,z)$-Clustering

###  3.1 Construction of the Coreset

The main goal of this section is to prove the following theorem:

######  Theorem 3.1.

Let $A$ be a set of $n$ points in $\mathbb{R}^{d}$, $\varepsilon>0$ and $k$ be
an integer. We can compute in deterministic time $k^{\log\log
k+\varepsilon^{-O(z)}}\cdot\text{poly}(nd)$ an $(\varepsilon,k,z)$-extension
partition coreset of $A$ with at most $k^{\varepsilon^{-O(z)}}$ distinct
points.

The key structural lemma we use in this case is as follows. Essentially, it
states that if the cost of clustering to a single center cannot be decreased
by adding $k$ centers, then the center is itself a partition coreset.

######  Lemma 3.2.

Let $A$ be a set of points in $\mathbb{R}^{d}$ and let $m$ be a (not
necessarily optimal) center for $A$. Let $M$ be the multiset of $|A|$ copies
of $m$.

Suppose that for all set of $k$ centers $\mathcal{S}$,

$\textsc{cost}(A,\\{m\\})-\textsc{cost}(A,\mathcal{S})<\alpha\cdot\textsc{cost}(A,\\{m\\}),$

for $\alpha\leq\frac{\varepsilon^{z+6}}{401408\cdot 2^{3z}\cdot z^{z+6}}$.

Then $M$ is an $(\varepsilon,k,z)$-extension partition coreset of $A$.

More precisely, define the function $f$ that maps $p$ to
$f(p)=\begin{pmatrix}m\\\ \|p-m\|\end{pmatrix}$, and let $M^{\prime}=f(A)$.
Then, for any partition $\mathcal{C}=\\{C_{1},...,C_{k}\\}$ of $A$ into $k$
parts and any centers $c_{1},...,c_{k}$ with $0$-extension
$c^{\prime}_{1},...,c^{\prime}_{k}$, it holds that

$\sum_{i=1}^{k}\sum_{p\in
C_{i}}\textsc{cost}(f(p),c^{\prime}_{i})=(1\pm\varepsilon)\sum_{i=1}^{k}\sum_{p\in
C_{i}}\textsc{cost}(p,c_{i})$

In other terms, the guarantee we have on $M$ is that fot any partition
$\mathcal{C}$ and any centers $c_{1},...,c_{k}$, it holds that

$\sum_{i=1}^{k}\sum_{p\in
C_{i}}\left(\|p-m\|^{2}+\|m-c_{i}\|^{2}\right)^{z/2}=(1\pm\varepsilon)\sum_{i=1}^{k}\sum_{p\in
C_{i}}\|p-c_{i}\|^{z}.$

Before proving this lemma, we will show why it implies the theorem.

###### Proof of Theorem 3.1.

The algorithm to construct the partition coreset is algorithm 1. In the
following, let $\beta$, and $\gamma$ be constants with a polynomial dependency
on $\varepsilon^{z}$ that we specify later.

Algorithm 1 PartitionCoreset($C,m$, depth)

1:Compute a set $\mathcal{S}$ for $(k,z)$-clustering on $C$, with cost
$(1+\beta)\textsc{cost}(C,\text{OPT}_{C})$ and with
$|\mathcal{S}|=O(k\log(1/\beta)/\beta)$, using the algorithm of theorem 2.6.

2:if
$\textsc{cost}(C,\\{m\\})-\textsc{cost}(C,\mathcal{S})\leq\beta\cdot\textsc{cost}(C,\\{m\\})$
then

3: Return a multiset $M$ with $|C|$ copies of $m$ as a partition coreset for
$C$, with extension $M^{\prime}=\left\\{\begin{pmatrix}m\\\
\|p-m\|\end{pmatrix},p\in C\right\\}$

4:else if depth = $\gamma$ then

5: Return a multiset $M$ with $|C|$ copies of $m$ as a partition coreset for
$C$, with extension $M^{\prime}=\left\\{\begin{pmatrix}m\\\
0\end{pmatrix},p\in C\right\\}$

6:else

7: Let $C_{1},...,C_{|\mathcal{S}|}$ be the clusters induced by $\mathcal{S}$,
with centers $c_{1},...,c_{|\mathcal{S}|}$

8: Return $\cup_{i=1}^{|\mathcal{S}|}$PartitionCoreset$(C_{i},c_{i},$
depth$+1)$.

We first argue that the algorithm is correct, namely,
PartitionCoreset$(P,0,0)$ computes a partition coreset. We will then show that
it runs in the desired (deterministic) time.

For the correctness, we proceed as follows. Let
$(C_{1},m_{1},d_{1}),(C_{2},m_{2},d_{2}),...$ be the set of calls to
PartitionCoreset that end in line 3. Let $M_{i}$ be the set computed for the
call with parameters $(C_{i},m_{i},d_{i})$. We show that for any $i$, $M_{i}$
is a partition coreset for $C_{i}$.

For this, we can use Lemma 3.2. Let us drop the subscript $i$ and fix $C,m$ to
be some $C_{i},m_{i}$, and let
$\beta=\frac{1}{2}\cdot\frac{\varepsilon^{z+6}}{401408\cdot 2^{3z}\cdot
z^{z+6}}$ (i.e.: equal to $\alpha/2$ with $\alpha$ being specified in Lemma
3.2). Let $\mathcal{S}$ be the solution computed line 1 of the algorithm for
$C$: for any set of $k$ centers $K$, it holds that
$\textsc{cost}(C,\mathcal{S})\leq(1+\beta)\textsc{cost}(C,K)$. Therefore, we
have:

$\displaystyle\textsc{cost}(C,\\{m\\})-\textsc{cost}(C,K)$ $\displaystyle\leq$
$\displaystyle\textsc{cost}(C,\\{m\\})-\frac{1}{1+\beta}\cdot\textsc{cost}(C,\mathcal{S})$
$\displaystyle=$
$\displaystyle\frac{1}{1+\beta}\left(\textsc{cost}(C,\\{m\\})-\textsc{cost}(C,\mathcal{S})\right)+\frac{\beta}{1+\beta}\cdot\textsc{cost}(C,\\{m\\})$
$\displaystyle\leq$
$\displaystyle\frac{\beta}{1+\beta}\cdot\textsc{cost}(C,\\{m\\})+\frac{\beta}{1+\beta}\cdot\textsc{cost}(C,\\{m\\})$
$\displaystyle\implies\textsc{cost}(C,\\{m\\})-\textsc{cost}(C,K)$
$\displaystyle\leq$ $\displaystyle 2\beta\cdot\textsc{cost}(C,\\{m\\}).$

Using Lemma 3.2, this implies that $M$ with its extension is indeed an
$\varepsilon$\- extension partition coreset for the points in $C$.

We now deal with the other termination criteria, namely when we reach depth
$\gamma$. For a level $\ell$, we define
$(C^{\ell}_{1},c^{\ell}_{1},\ell),(C^{\ell}_{2},c^{\ell}_{2},\ell),...$ be the
set of calls to PartitionCoreset with level$=\ell$, and let $\Gamma=\cup
C^{\gamma}_{i}$, $\mathcal{S}_{\Gamma}=\cup c^{\gamma}_{i}$. One can easily
show that
$\sum_{i}\textsc{cost}(C^{\ell}_{i},c^{\ell}_{i})\leq\frac{1}{1+\beta}\sum_{i}\textsc{cost}(C^{\ell-1}_{i},c^{\ell-1}_{i})$,
as if the cost does not decrease by $\frac{1}{1+\beta}$ then the recursion
stops on line 3. Hence, the cost of clustering $\Gamma$ to
$\mathcal{S}_{\Gamma}$ is $\textsc{cost}(\Gamma,\mathcal{S}_{\Gamma})\leq
z^{O(z)}\cdot\left(\frac{1}{1+\beta}\right)^{\gamma}\text{OPT}$, where OPT is
the optimal cost for $(k,z)$-clustering on the full dataset. We define
$\gamma$ such that
$2^{O(z)}\cdot\left(\frac{1}{1+\beta}\right)^{\gamma}\leq\left(\frac{\varepsilon}{8z}\right)^{z}$:
this holds when
$\gamma=\Omega\left(\frac{z\log\left(\frac{8z^{2}}{\varepsilon}\right)}{\log(1+\beta)}\right)$,
and so $\gamma\in O(\varepsilon^{-O(z)})$ as desired. For each point
$p\in\Gamma$, let $c_{p}$ be its center in the solution
$\mathcal{S}_{\Gamma}$. Now we consider a set of at most $k$ centers $K$, and
denote $K_{p}$ the center to which $p\in\Gamma$ is assigned. We have

$\displaystyle\left|\sum_{p\in\Gamma}\textsc{cost}(p,K)-\textsc{cost}(c_{p},K)\right|$
$\displaystyle(Lem.~{}\ref{lem:weaktri})$ $\displaystyle\leq$
$\displaystyle\sum_{p\in\Gamma}\varepsilon/2\cdot\textsc{cost}(p,K)+\left(\frac{4z+\varepsilon}{\varepsilon}\right)^{z-1}\cdot\textsc{cost}(p,c_{p})$
$\displaystyle(\text{Cost of }\Gamma)$ $\displaystyle\leq$
$\displaystyle\varepsilon/2\cdot\textsc{cost}(\Gamma,K)+\left(\frac{4z+\varepsilon}{\varepsilon}\right)^{z-1}\cdot\left(\frac{\varepsilon}{8z}\right)^{z}\cdot\text{OPT}$
$\displaystyle\leq$
$\displaystyle\varepsilon/2\textsc{cost}(A,K)+\varepsilon/2\cdot\text{OPT}\leq\varepsilon\cdot\textsc{cost}(A,K),$

Therefore, the set $M_{\Gamma}$ with its extension
$M^{\prime}_{\Gamma}=\left\\{\begin{pmatrix}c_{p}\\\
0\end{pmatrix},p\in\Gamma\right\\}$ is indeed a partition coreset for
$\Gamma$.

By linearity of the function cost, this implies that partitionCoreset$(P,0,0)$
indeed compute an $(\varepsilon,z,k)$-extension partition coreset of $P$:
$M_{i}$ is an $(\varepsilon,z,k)$-extension partition coreset for $C_{i}$,
$M_{\gamma}$ is one for $\Gamma$, and $P$ is the disjoint union of $\Gamma$
and the $C_{i}$.

The size of that coreset (i.e., the number of distinct points when removing
the last coordinate) is the number of recursion call in the algorithm, which
is at most $k^{\varepsilon^{-O(z)}}$ by an easy induction: when the level is
less than $\gamma$, a set $C$ is divided into
$O(k\cdot\log(1/\beta)/\beta)=k\cdot(z/\varepsilon)^{z+O(1)}$ clusters, and
there are $\gamma\in O\left(\varepsilon^{-O(z)}\right)$ many levels.

We now consider the running time. The algorithm of theorem 2.6 runs in time
$k^{\log\log k+\log(1/\varepsilon)}\cdot\text{poly}(nd)$. It is used once per
cluster of each level, hence as above at most $k^{\varepsilon^{-O(z)}}$ many
times before terminating, and therefore a total complexity of $k^{\log\log
k+\varepsilon^{-O(z)}}\cdot\text{poly}(nd)$.

To make explicit the polynomial in $\varepsilon$ in the particular case where
$z=1$ (resp. $z=2$), note that $\beta$ is essentially $\varepsilon^{z+6}$, and
therefore $\gamma\approx 1/\log(1+\beta)\approx\varepsilon^{-z-6}$. The number
of recursion call and size of the coreset is therefore
$k^{\varepsilon^{-z-6}}$. ∎

The remaining part of this section will now be devoted to proving Lemma 3.2.

###  3.2 Proof of the Structural Lemma 3.2

We first require a bit of notation. Fix a partition into $k$ parts
$\mathcal{C}=\\{C_{1},...,C_{k}\\}$ and let $\\{c_{1},\ldots c_{k}\\}$ be the
centers.

For every point $p\in C_{i}$, we denote by $q_{p}$ the projection of $p$ onto
the line through $m$ and $c_{i}$. Let $Q_{i}$ be the multiset of projections
of the points in $C_{i}$. By the Pythagorean theorem, we have for any $p\in
C_{i}$:

$\|p-c_{i}\|=\sqrt{\|p-q_{p}\|^{2}+\|q_{p}-c_{i}\|^{2}}.$

Our goal is to show that for “most” of the points $p\in A$ one of the
following conditions hold.

Cond. 1

$\|p-m\|\geq\left(\frac{4z}{\varepsilon}\right)\cdot\|m-c_{i}\|$ or
$\|p-m\|\leq\left(\frac{\varepsilon}{4z}\right)\cdot\|m-c_{i}\|$ (i.e. the
conditions of Lemma 3.3 below are met) or

Cond. 2

$\|q_{p}-m\|\leq\varepsilon/(7z)\cdot\|p-m\|$ (i.e. the conditions of Lemma
3.4 below are met).

The following two lemmas show that if we can assume that one of these two
cases hold, then the points in $M^{\prime}$ corresponding to the point $p$ is
a good proxy for $\|p-c_{i}\|^{z}$. We will deal afterwards in lemma 3.5 with
points satisfying neither of the conditions.

######  Lemma 3.3.

If either $\|p-m\|\geq\left(\frac{4z}{\varepsilon}\right)\cdot\|m-c_{i}\|$ or
$\|p-m\|\leq\left(\frac{\varepsilon}{4z}\right)\cdot\|m-c_{i}\|$ then

$\left|\left(\|p-m\|^{2}+\|m-c_{i}\|^{2}\right)^{z/2}-\|p-c_{i}\|^{z}\right|\leq\varepsilon\cdot\left(\|p-m\|^{z}+\|p-c_{i}\|^{z}\right).$

###### Proof.

Condition 1 essentially says that $m$ is either really close to $p$ or to
$c_{i}$. In the first case, $\|p-m\|^{2}$ is negligible, and
$\|p-c_{i}\|\approx\|m-c_{i}\|$. In the second case, $\|m-c_{i}\|$ negligible
and $\|p-c_{i}\|\approx\|p-m\|$. We formalize this argument below.

We first show that Condition 1 implies
$\|p-c_{i}\|^{z}=(1\pm\varepsilon/2)\max(\|p-m\|^{z},\|m-c_{i}\|^{z})$.
Indeed, we have:

$\displaystyle\max(\|p-m\|,\|m-c_{i}\|)-\min(\|p-m\|,\|m-c_{i}\|)\geq(1-\varepsilon/(4z))\cdot\max(\|p-m\|,\|m-c_{i}\|)$
$\displaystyle\max(\|p-m\|,\|m-c_{i}\|)+\min(\|p-m\|,\|m-c_{i}\|)\leq(1+\varepsilon/(4z))\cdot\max(\|p-m\|,\|m-c_{i}\|)$

Using the Mercator series, it holds that
$(1+\varepsilon/(4z))^{z}=e^{z\cdot\ln(1+\varepsilon/(4z))}\leq
e^{\varepsilon/4}\leq e^{\ln(1+\varepsilon/2)}=1+\varepsilon/2$: therefore,

$\displaystyle\|p-c_{i}\|^{z}$ $\displaystyle\leq$
$\displaystyle(\|p-m\|+\|m-c_{i}\|)^{z}$ $\displaystyle\leq$
$\displaystyle(1+\varepsilon/2)\cdot\max(\|p-m\|^{z},\|m-c_{i}\|^{z})$

Using Bernoulli’s inequality, $(1-\varepsilon/(4z))^{z}\geq 1-\varepsilon/4$:
therefore,

$\displaystyle\|p-c_{i}\|^{z}$ $\displaystyle\geq$
$\displaystyle\left(\max(\|p-m\|,\|m-c_{i}\|)-\min(\|p-m\|,\|m-c_{i}\|)\right)^{z}$
$\displaystyle\geq$
$\displaystyle(1-\varepsilon/(4z))^{z}\cdot\max(\|p-m\|^{z},\|m-c_{i}\|^{z})$
$\displaystyle\geq$
$\displaystyle(1-\varepsilon/2)\cdot\max(\|p-m\|^{z},\|m-c_{i}\|^{z}).$

We bound similarly the other term of the expression:

$\displaystyle\left(\|p-m\|^{2}+\|m-c_{i}\|^{2}\right)^{z/2}$
$\displaystyle\leq$
$\displaystyle\left((1\pm\varepsilon/(4z))\cdot\max(\|p-m\|^{2},\|m-c_{i}\|^{2})\right)^{z/2}$
$\displaystyle\leq$
$\displaystyle(1\pm\varepsilon/2)\cdot\max(\|p-m\|^{z},\|m-c_{i}\|^{z})$

Combining those expressions, we obtain

$\displaystyle\left|\left(\|p-m\|^{2}+\|m-c_{i}\|^{2}\right)^{z/2}-\|p-c_{i}\|^{z}\right|$
$\displaystyle=$
$\displaystyle\big{|}(1\pm\varepsilon/2)\cdot\max(\|p-m\|^{z},\|m-c_{i}\|^{z})-(1\pm\varepsilon/2)\cdot\max(\|p-m\|^{z},\|m-c_{i}\|^{z})\big{|}$
$\displaystyle\leq$
$\displaystyle\varepsilon\cdot(\|p-m\|^{z}+\|p-c_{i}\|^{z})$

∎

######  Lemma 3.4.

Let $p,m,c_{i}\in\mathbb{R}^{d}$. Denote by $q_{p}$ the orthogonal projection
of $p$ onto the line through $m$ and $c_{i}$. Then if for
$0\leq\varepsilon\leq 1/2$ and $z\geq 1$

$\|m-q_{p}\|\leq\varepsilon/(7z)\cdot\|p-m\|,$

we have:

$\left|\left(\|p-m\|^{2}+\|m-c_{i}\|^{2}\right)^{z/2}-\|p-c_{i}\|^{z}\right|\leq\varepsilon\cdot\|p-c_{i}\|^{z}.$

###### Proof.

This theorem states that when the projection of $p$ on the line between $m$
and $c_{i}$ is really close to $m$, then Pythagorean theorem almost hold
between $p,m$ and $c_{i}$. To show this, we first require a lower bound on
$\|p-c_{i}\|$ in terms of $\|p-m\|$. We have, using the assumption on
$\|m-q_{p}\|$:

$\displaystyle\|p-c_{i}\|^{2}$ $\displaystyle\geq$
$\displaystyle\|p-q_{p}\|^{2}\geq\|p-m\|^{2}-\|q_{p}-m\|^{2}$ (1)
$\displaystyle\geq$
$\displaystyle\|p-m\|^{2}\cdot(1-\varepsilon^{2}/(49z^{2}))$

Using the Pythagorean theorem, we can relate $\|p-m\|^{2}$ to $\|p-c_{i}\|$ as
follows:
$\|p-m\|^{2}=\|p-q_{p}\|^{2}+\|q_{p}-m\|^{2}+\|q_{p}-c_{i}\|^{2}-\|q_{p}-c_{i}\|^{2}=\|p-c_{i}\|^{2}+\|q_{p}-m\|^{2}-\|q_{p}-c_{i}\|^{2}$

Combined with Lemma 2.5, we get the following:

$\displaystyle\|p-m\|^{2}+\|m-c_{i}\|^{2}$ $\displaystyle=$
$\displaystyle\|p-c_{i}\|^{2}+\|q_{p}-m\|^{2}-\|q_{p}-c_{i}\|^{2}+\|m-c_{i}\|^{2}$
$\displaystyle=$
$\displaystyle\|p-c_{i}\|^{2}+\|q_{p}-m\|^{2}\pm\left(\frac{\varepsilon}{4z}\cdot\|q_{p}-c_{i}\|^{2}+\left(1+\frac{4z}{\varepsilon}\right)\|q_{p}-m\|^{2}\right)$
$\displaystyle=$
$\displaystyle\|p-c_{i}\|^{2}\pm\left(\frac{\varepsilon}{4z}\cdot\|q_{p}-c_{i}\|^{2}+\left(2+\frac{4z}{\varepsilon}\right)\|q_{p}-m\|^{2}\right)$

Now, using that $\|q_{p}-c_{i}\|\leq\|p-c_{i}\|$ (since a projection decreases
distances) and the assumption on $\|m-q_{p}\|$, we get:

$\displaystyle\|p-m\|^{2}+\|m-c_{i}\|^{2}$ $\displaystyle=$
$\displaystyle(1\pm\varepsilon/(4z))\|p-c_{i}\|^{2}\pm\left(\frac{2\varepsilon+4z}{\varepsilon}\right)\cdot\frac{\varepsilon^{2}}{49z^{2}}\cdot\|p-m\|^{2}$
$\displaystyle(Eq.~{}\ref{eq:projbound1})$ $\displaystyle=$
$\displaystyle(1\pm\varepsilon/(4z))\|p-c_{i}\|^{2}\pm\left(\frac{2\varepsilon+4z}{\varepsilon}\right)\cdot\frac{\varepsilon^{2}}{49z^{2}}\cdot\frac{1}{1-\frac{\varepsilon^{2}}{49z^{2}}}\cdot\|p-c_{i}\|^{2}$
$\displaystyle(\varepsilon<\frac{1}{2})$ $\displaystyle=$
$\displaystyle(1\pm\varepsilon/(2z))\|p-c_{i}\|^{2}$

We can conclude, using again the Mercator series and Bernoulli’s inequality:

$\displaystyle\left|\left(\|p-m\|^{2}+\|m-c_{i}\|^{2}\right)^{z/2}-\|p-c_{i}\|^{z}\right|$
$\displaystyle=$
$\displaystyle\left|(1\pm\varepsilon/(2z))^{z}\cdot\|p-c_{i}\|^{z}-\|p-c_{i}\|^{z}\right|$
$\displaystyle=$
$\displaystyle\left|(1\pm\varepsilon)\|p-c_{i}\|^{z}-\|p-c_{i}\|^{z}\right|\leq\varepsilon\cdot\|p-c_{i}\|^{z}$

∎

We now bound the cost of the remaining points. Let $D$ be the set of points
that satisfy neither conditions, i.e. for every point $p\in D$ we have

$\left(\frac{\varepsilon}{4z}\right)\cdot\|m-c_{i}\|\leq\|p-m\|\leq\left(\frac{4z}{\varepsilon}\right)\cdot\|m-c_{i}\|$
(2)

and

$\|q_{p}-m\|\geq\varepsilon/(7z)\cdot\|p-m\|.$ (3)

Those two conditions allow us to relate the cost of clustering the points to
$m$ and the cost of solution $\mathcal{S}$. Using the additional property of
$\mathcal{S}$, we can show that the contribution of the points in $D$ to the
clustering cost of $m$ is small.

######  Lemma 3.5.

Let $m$ be a point such that there exists no solution $\mathcal{S}$ with $k$
centers and
$\textsc{cost}(A,\\{m\\})-\textsc{cost}(A,\mathcal{S})\leq\alpha\cdot\textsc{cost}(A,\\{m\\})$.

Suppose $\mathcal{C}=\\{C_{1},...,C_{k}\\}$ is a partition with corresponding
centers $\\{c_{1},...,c_{k}\\}$ and let $D$ be the set of points that satisfy
neither condition (1) nor condition (2). It must be that

$\sum_{p\in
D}\|p-m\|^{z}<\alpha\cdot\frac{25088z^{6}}{\varepsilon^{6}}\cdot\sum_{p\in
A}\|p-m\|^{z}.$

###### Proof.

The high level idea of the proof is to show the existence of a set of $k$
centers $T$ that decreases the cost of $D$ by a significant factor. This
implies that the cost of $D$ must be small compared to the overall cost.

Consider a center $c_{i}$ and let
$\ell_{i}=m+(m-c_{i})\cdot\frac{\varepsilon^{2}}{28z^{2}}$ and
$r_{i}=m+(m-c_{i})\cdot\frac{\varepsilon^{2}}{28z^{2}}$. Let $B$ be union of
all $\ell_{i}$ and $r_{i}$. We assign each point $p\in D\cap C_{i}$ to its
closest center $b_{i}\in\\{\ell_{i},r_{i}\\}$. Note that due to Equations 2
and 3
$\|q_{p}-m\|\geq\frac{\varepsilon}{7z}\cdot\|p-m\|\geq\frac{\varepsilon^{2}}{28z^{z}}\cdot\|m-c_{i}\|=\|b_{i}-m\|$.
Using the Pythagorean theorem, we then have

$\displaystyle\|p-b_{i}\|^{z}$ $\displaystyle=$
$\displaystyle\left(\|p-q_{p}\|^{2}+\|q_{p}-b_{i}\|^{2}\right)^{z/2}$
$\displaystyle\leq$
$\displaystyle\left(\|p-q_{p}\|^{2}+\|q_{p}-m\|^{2}-\|b_{i}-m\|^{2}\right)^{z/2}$
$\displaystyle=$
$\displaystyle\left(\|p-m\|^{2}-\left(\frac{\varepsilon^{2}}{28z^{2}}\right)^{2}\cdot\|m-c_{i}\|^{2}\right)^{z/2}$
$\displaystyle(Eq.~{}\ref{eq:key1})$ $\displaystyle\leq$
$\displaystyle\left(\|p-m\|^{2}-\frac{\varepsilon^{6}}{12544z^{6}}\cdot\|p-m\|^{2}\right)^{z/2}$
$\displaystyle=$
$\displaystyle\|p-m\|^{z}\cdot(1-\frac{\varepsilon^{6}}{12544z^{6}})$

Summing this over all points therefore leads to a cost decrease of at least

$\displaystyle\sum_{p\in D}\|p-m\|^{z}-\sum_{p\in
D}\|p-b_{i}\|^{z}\geq\frac{\varepsilon^{6}}{12544z^{6}}\cdot\sum_{p\in
D}\|p-m\|^{z}.$

Since we use $2k$ centers, the average cost decrease per center is
$\frac{1}{2k}\cdot\frac{\varepsilon^{6}}{800z^{6}}\cdot\sum_{p\in
D}\|p-m\|^{z}$. We greedily pick the $k$ centers with maximum cost decrease.
Denote this set $T$ and denote the set of points with cost decrease by
$D_{T}$. By Markov’s inequality, we therefore have

$\displaystyle\sum_{p\in D_{T}}\|p-m\|^{z}-\sum_{p\in
D_{T}}\|p-b_{i}\|^{z}\geq\frac{\varepsilon^{6}}{25088z^{6}}\cdot\sum_{p\in
D}\|p-m\|^{z}.$

Since we assumed that no clustering exists decreasing the cost by more than
$\alpha\cdot\sum_{p\in A}\|p-m\|^{z}$, this implies

$\displaystyle\frac{\varepsilon^{6}}{25088z^{6}}\cdot\sum_{p\in
D}\|p-m\|^{z}\leq\alpha\cdot\sum_{p\in A}\|p-m\|^{z}$
$\displaystyle\Rightarrow\sum_{p\in
D}\|p-m\|^{z}\leq\alpha\cdot\frac{25088z^{6}}{\varepsilon^{6}}\cdot\sum_{p\in
A}\|p-m\|^{z}.$

∎

######  Remark 3.6.

The dependency on $\varepsilon$ can be improved to at least
$\varepsilon^{-4}$, using a more involved analysis to determine the cost of a
cheaper clustering $T$. Since the subsequent analysis incurs a dependency
$\varepsilon^{-z}$, we chose the simpler proof in favour of optimizing lower
order terms in the exponent of $\varepsilon$.

We can now conclude the proof of Lemma 3.2.

###### Proof of Lemma 3.2.

Recall that for $p\in A$, we defined $f(p)=\begin{pmatrix}m\\\
\|p-m\|\end{pmatrix}$, and for any center $c_{i}$,
$c^{\prime}_{i}=\begin{pmatrix}c_{i}\\\ 0\end{pmatrix}$. We have, using the
Pythagorean theorem and triangle inequality:

$\displaystyle\left|\sum_{i=1}^{k}\sum_{p\in
C_{i}}\textsc{cost}(p,c_{i})-\sum_{i=1}^{k}\sum_{p\in
C_{i}}\textsc{cost}(f(p),c^{\prime}_{i})\right|$ (5) $\displaystyle=$
$\displaystyle\left|\sum_{i=1}^{k}\sum_{p\in
C_{i}}\|p-c_{i}\|^{z}-\left(\|m-p\|^{2}+\|m-c_{i}\|^{2}\right)^{z/2}\right|$
$\displaystyle\leq$ $\displaystyle\left|\sum_{i=1}^{k}\sum_{p\in
C_{i}\setminus
D}\|p-c_{i}\|^{z}-\left(\|m-p\|^{2}+\|m-c_{i}\|^{2}\right)^{z/2}\right|$
$\displaystyle+\left|\sum_{i=1}^{k}\sum_{p\in C_{i}\cap
D}\|p-c_{i}\|^{z}-\left(\|m-p\|^{2}+\|m-c_{i}\|^{2}\right)^{z/2}\right|.$

The term in Equation 5 can be bounded using Lemmas 3.3 and 3.4 by

$\sum_{i=1}^{k}\sum_{p\in C_{i}\setminus
D}\varepsilon\cdot(\|p-c_{i}\|^{z}+\|p-m\|^{z})\leq\varepsilon\cdot\left(\sum_{i=1}^{k}\textsc{cost}(C_{i},\\{c_{i}\\})+\sum_{i=1}^{k}\textsc{cost}(C_{i},\\{m\\})\right).$

For the term in Equation 5, we use a looser bound and lemma 3.5 as follows:

$\displaystyle\left|\sum_{i=1}^{k}\sum_{p\in C_{i}\cap
D}\|p-c_{i}\|^{z}-\left(\|m-p\|^{2}+\|m-c_{i}\|^{2}\right)^{z/2}\right|$
$\displaystyle\leq$ $\displaystyle 2^{z+1}\sum_{i=1}^{k}\sum_{p\in C_{i}\cap
D}\max(\|p-c_{i}\|^{z},\|m-c_{i}\|^{z})$ $\displaystyle(Eq.~{}\ref{eq:key1})$
$\displaystyle\leq$ $\displaystyle 2^{z+1}\sum_{p\in
D}\left(1+\left(\frac{4z}{\varepsilon}\right)^{z}\right)\cdot\|p-m\|^{z}$
$\displaystyle(Lem.~{}\ref{lem:badcost})$ $\displaystyle\leq$ $\displaystyle
2^{z+2}\cdot\left(\frac{4z}{\varepsilon}\right)^{z}\cdot\alpha\cdot\frac{25088z^{6}}{\varepsilon^{6}}\cdot\sum_{p\in
A}\|p-m\|^{z}$ (6)

Combining with lemma 3.3 and lemma 3.4, we then obtain:

$\displaystyle\left|\sum_{i=1}^{k}\textsc{cost}(C_{i},\\{c_{i}\\})-\sum_{i=1}^{k}\textsc{cost}(f(C_{i}),\\{c^{\prime}_{i}\\})\right|$
$\displaystyle(Lem.~{}\ref{lem:tighterbound}\text{ and }\ref{lem:projbound})$
$\displaystyle\leq$
$\displaystyle\varepsilon\cdot\left(\sum_{i=1}^{k}\textsc{cost}(C_{i},\\{c_{i}\\})+\sum_{i=1}^{k}\textsc{cost}(C_{i},\\{m\\})\right)$
$\displaystyle(Eq.~{}\ref{eq:keyfinal})$
$\displaystyle+2^{z+2}\cdot\left(\frac{4z}{\varepsilon}\right)^{z}\cdot\alpha\cdot\frac{25088z^{6}}{\varepsilon^{6}}\cdot\textsc{cost}(A,\\{m\\})$
$\displaystyle(\text{no cost decrease})$ $\displaystyle\leq$ $\displaystyle
2\cdot\left(2\varepsilon+2^{z+2}\cdot\left(\frac{4z}{\varepsilon}\right)^{z}\cdot\alpha\cdot\frac{25088z^{6}}{\varepsilon^{6}}\right)\cdot\sum_{i=1}^{k}\textsc{cost}(C_{i},\\{c_{i}\\})$

The overall result now follows by our choice of $\alpha$ and rescaling
$\varepsilon$. ∎

##  4 Derandomized Dimension Reduction

In this section we will use the deterministic construction of partition
coresets to obtain a derandomized dimension reduction for $(k,z)$ clustering.
The goal is to show that we can obtain a cost preserving sketch with dimension
at most $O(\varepsilon^{-O(z)}\log k)$:

######  Theorem 4.1.

Let $P\subset\mathds{R}^{d}$. We can compute an $(k,z,\varepsilon)$-cost
preserving sketch of $P$ with target dimension
$O\left(\varepsilon^{-O(z)}\cdot\log k\right)$ in deterministic time
$k^{\log\log k+\varepsilon^{-O(z)}}\cdot\text{poly}(nd)$.

In the particular $k$-median case ($z=1$), the precise target dimension is
$\varepsilon^{-11}\log k$, while it is $\varepsilon^{-12}\log k$ for
$k$-means. We did not make any particular attempt to optimize the dependency
in $\varepsilon$.

Again, the first-thought approach would be to use the deterministic Johnson-
Lindenstrauss transform of [EIO02] (Theorem 2.7). Unfortunately, merely
preserving pairwise distances is not sufficient to preserve the cost to an
optimal $(1,z)$-center, except for the special case $z=2$. Instead, we
introduce the following notion.

######  Definition 4.2 (Witness Sets).

Let $P$ be a set of $n$ points in $\mathbb{R}^{d}$ (with a possible extension
coordinate), let $c$ be an optimal $(1,z)$-center (under the possible
constraint that the extension coordinate is 0) and let
$\Delta=\frac{\sum_{p\in P}\|p-c\|^{z}}{n}$. Then a
$(D,R,\varepsilon)$-uniform witness set is a subset $S\subset P$ such that

  * •

The convex hull of $S$ contains a $(1+\varepsilon)$-approximation of
$(1,z)$-clustering on $P$ (under the possible constraint that the extension
coordinate is 0).

  * •

The diameter of $S$ is at most $D\cdot\sqrt[z]{\Delta}$.

  * •

The size of $S$ is at most $R$.

The first important result is proving that the existence of witness sets of
small size exist for a specific range of parameters.

######  Theorem 4.3.

There exists $\left(\frac{O(z)}{\varepsilon},\varepsilon^{-2}\cdot
2^{O(z)},\varepsilon\right)$ witness sets.

We give a full proof of Theorem 4.3 in Section A of the appendix. The
existence of small witness sets is essentially a consequence of the existence
of small coresets. Let us consider how this existence of small witness sets
combined with Theorem 3.1 implies that we can deterministically construct a
cost preserving sketch for powers.

The main idea is that the property of witness sets allows us to efficiently
“discretize” all candidate solutions in the convex hull of a witness set. We
will show that the dimension reduction preserves the property of a subset of
points being a witness set. Furthermore, because witness sets lie in low-
dimensional spaces, we can guarantee that the cost for every point in the
convex hull of a witness is preserved. Specifically, we use that linear
projections preserve subspaces, and in particular the subspace spanned by the
points in the convex hull of the witness set. Hence, if the cost of every
candidate solution in a witness set stays the same, up to a
$(1\pm\varepsilon)$ factor, the clustering cost overall also stays the same.

######  Lemma 4.4.

Let $P\subset\mathds{R}^{d}$ be a a multiset with at most $T$ distinct points.
There exists a set $\mathcal{N}$ of size $T^{O\left(\varepsilon^{-2}\right)}$
that can be computed in deterministic time
$T^{O\left(\varepsilon^{-2}\right)}$ with the following property. If a linear
projection $\Pi$ preserves pairwise distances between points of $\mathcal{N}$
up to a $(1\pm\varepsilon/z)$ error, then:

for any extension $P^{\prime}$ of $P$ where each point $p$ has coordinate
extension $p^{\prime}$, and for any subset $C$ of $P$ (with extension
$C^{\prime}$),

$\sum_{p\in C}\left\|\begin{pmatrix}\Pi p\\\
p^{\prime}\end{pmatrix}-\mu^{z}_{0}(\Pi^{\prime}(C))\right\|^{z}=(1\pm\varepsilon)\sum_{p\in
C}\left\|\begin{pmatrix}p\\\
p^{\prime}\end{pmatrix}-\mu^{z}_{0}(C^{\prime})\right\|^{z},$

where $\Pi^{\prime}(C):=\left\\{\begin{pmatrix}\Pi p\\\
p^{\prime}\end{pmatrix},p\in C\right\\}$ is the projection of $C$ with the
same extensions as $C^{\prime}$.

###### Proof.

First, $\mathcal{N}$ is constructed as follows. Let
$\varepsilon^{\prime}=\varepsilon/(4Dz)$, where $D=O(z)/\varepsilon$ is the
first parameter of the witness set provided in theorem 4.3. For each possible
set $S\subseteq P$ of size $O(1/\varepsilon^{2})$, construct an
$\varepsilon^{\prime}\cdot\text{diam}(S)$-cover of the convex hull of
$S$.444Recall that a $\varepsilon$-cover of a set $S$ is a set of points $N$
such that for an $x\in S$, we have some $y\in N$ with
$\|x-y\|\leq\varepsilon$. Moreover, let $V$ be an orthogonal basis of the
subspace spanned by $S$, with the addition of the origin.

$\mathcal{N}$ is made of the union of those covers and basis, for all possible
sets $S$. To bound its size, observe that each set $S$ lies in an
$|S|=O\left(\varepsilon^{-2}\right)$-dimensional flat. Hence, we can compute
an $\varepsilon^{\prime}\text{diam}(S)$-cover of $S$ of size at most
$\left(\frac{O(\sqrt{|S|})}{\varepsilon^{\prime}}\right)^{|S|}=\varepsilon^{-O(\varepsilon^{-2})}$
in deterministic time polynomial in $\varepsilon^{-O(\varepsilon^{-2})}$
[Cha01]. Similarly, we can compute the basis $V$ in deterministic polynomial
time.

Since there are at most $T^{O(\varepsilon^{-2})}$ many different set $S$, the
size of $\mathcal{N}$ is therefore bounded by

$T^{O\left(\varepsilon^{-2}\right)}\cdot\varepsilon^{-O(\varepsilon^{-2})}=T^{O\left(\varepsilon^{-2}\right)}.$

We now verify that $\mathcal{N}$ has the desired property. Essentially,
preserving the norm of each basis $V$ will ensure that the operator norm of
$\Pi$ is bounded, and preserving the distances to all net points, combined
with the existance of small witness set, will guarantee that the clustering
cost is preserved.

Let $P^{\prime}$ be an extension of $P$ as in the lemma statement, and define
$\mathcal{N}^{\prime}$ to be the set of $0$-extensions of $\mathcal{N}$. We
first note that any possible witness set $S^{\prime}$ for $P^{\prime}$ under
the constraint that the extension coordinate is $0$, an
$\varepsilon^{\prime}\text{diam}(S^{\prime})$-cover of
$\text{conv}(S^{\prime})\cap\\{x\in\mathds{R}^{d+1}:x_{d+1}=0\\}$ is contained
in $\mathcal{N}^{\prime}$. Indeed, let $S$ be the corresponding witness set
for $P$ (i.e., $S^{\prime}$ where we removed the extension coordinate): it
holds that
$\text{conv}(S^{\prime})\cap\\{x\in\mathds{R}^{d+1}:x_{d+1}=0\\}\subseteq\text{conv}(S)$,
and $\text{diam}(S)\leq\text{diam}(S^{\prime})$, so the
$\varepsilon^{\prime}\text{diam}(S)$ cover of $\text{conv}(S)$ is also an
$\varepsilon^{\prime}\text{diam}(S^{\prime})$-cover of
$\text{conv}(S^{\prime})\cap\\{x\in\mathds{R}^{d+1}:x_{d+1}=0\\}$.

Let $\Pi$ be a linear projection such that the distance from any point of $P$
to any point of $\mathcal{N}$ is preserved up to an error
$(1\pm\varepsilon/z)$, and $C$ be a subset of $P$. As in the lemma statement,
we define $\Pi^{\prime}(C):=\left\\{\begin{pmatrix}\Pi p\\\
p^{\prime}\end{pmatrix},p\in C\right\\}$. What we need to show is that
$\textsc{P-cost}_{0}(\Pi^{\prime}(C))=(1\pm\varepsilon)\textsc{P-cost}_{0}(C^{\prime})$
or, in other terms,

$\sum_{p\in C}\left\|\begin{pmatrix}p\\\
p^{\prime}\end{pmatrix}-\mu^{z}_{0}(C^{\prime})\right\|^{z}=(1\pm\varepsilon)\sum_{p\in
C}\left\|\begin{pmatrix}\Pi p\\\
p^{\prime}\end{pmatrix}-\mu^{z}_{0}(\Pi^{\prime}(C))\right\|^{z},$

We first prove the somewhat easier direction which states that the cost does
not increase with the projection. Let $S^{\prime}$ be a
$(D,R,\varepsilon^{\prime})$-witness set for $C^{\prime}$ given by theorem
4.3. Denote by $c^{*}$ the point whose $0$-extension is in the convex hull of
$S^{\prime}$ which is the $(1+\varepsilon)$-approximate solution to
$\mu^{z}_{0}(C^{\prime})$, and $c$ the point of $\mathcal{N}$ closest to
$c^{*}$. We will show that $\begin{pmatrix}\Pi c\\\ 0\end{pmatrix}$ is a good
center for $\Pi^{\prime}(C)$.

Since $\mathcal{N}$ contains an $\varepsilon^{\prime}\text{diam}(S)$-cover of
$\text{conv}(S)$ and $S$ is a witness set, we have

$\|c^{*}-c\|\leq\varepsilon^{\prime}\cdot\text{diam}(S)\leq\varepsilon^{\prime}\cdot
D\cdot\left(\frac{\textsc{P-cost}_{0}(C^{\prime})}{|C|}\right)^{1/z}$ (7)

Let $\Delta_{C}:=\frac{\textsc{P-cost}_{0}(C^{\prime})}{|C|}$. We have, for
any point $p$:

$\displaystyle\|\Pi p-\Pi c\|$ $\displaystyle(\text{Distortion of Embedding})$
$\displaystyle\leq$ $\displaystyle(1+\varepsilon/z)\cdot\|p-c\|$
$\displaystyle\leq$
$\displaystyle(1+\varepsilon/z)\cdot\left(\|p-c^{*}\|+\|c^{*}-c\|\right)$
$\displaystyle(Eq.~{}\ref{eq:derandom1})$ $\displaystyle\leq$
$\displaystyle(1+\varepsilon/z)\cdot\left(\|p-c^{*}\|+\varepsilon^{\prime}\cdot
D\cdot\Delta_{C}^{1/z}\right)$ $\displaystyle(\text{choice of
}\varepsilon^{\prime})$ $\displaystyle\leq$
$\displaystyle(1+\varepsilon/z)\cdot\left(\|p-c^{*}\|+\varepsilon/(2z)\cdot\Delta_{C}^{1/z}\right)$

Therefore, using lemma 2.5, we get $\|\Pi p-\Pi
c\|\leq(1+\varepsilon/z)^{3}(\|p-c^{*}\|^{2}+\frac{\varepsilon}{2z}\Delta_{C}^{2/z})$.
Since the embedding of $c$ is $\begin{pmatrix}\Pi c\\\ 0\end{pmatrix}$, we
obtain:

$\displaystyle\left\|\begin{pmatrix}\Pi p\\\
p^{\prime}\end{pmatrix}-\begin{pmatrix}\Pi c\\\ 0\end{pmatrix}\right\|^{z}$
$\displaystyle=\left(\|\Pi p-\Pi c\|^{2}+p^{\prime 2}\right)^{z/2}$
$\displaystyle\leq\left((1+\varepsilon/z)^{3}\cdot\left(\|p-c^{*}\|^{2}+\frac{\varepsilon}{2z}\cdot(\Delta_{C})^{2/z}\right)+{p^{\prime}}^{2}\right)^{z/2}$
$\displaystyle\leq(1+\varepsilon/z)^{3z/2}\cdot\left((\|p-c^{*}\|^{2}+{p^{\prime}}^{2})+\frac{\varepsilon}{2z}\cdot(\Delta_{C})^{2/z}\right)^{z/2}$
$\displaystyle\leq(1+\varepsilon/z)^{3z/2}\left((1+\varepsilon)\cdot(\|p-c^{*}\|^{2}+{p^{\prime}}^{2})^{z/2}+\left(\frac{z+\varepsilon}{\varepsilon}\right)^{z/2-1}\left(\frac{\varepsilon}{2z}\right)^{z/2}\cdot\Delta_{C}\right)$
$\displaystyle\leq(1+3\varepsilon)\cdot(\|p-c^{*}\|^{2}+{p^{\prime}}^{2})^{z/2}+\varepsilon\cdot\Delta_{C}$

Summing over all $p\in C$, we get that

$\displaystyle\textsc{P-cost}_{0}(\Pi^{\prime}(C))$
$\displaystyle\leq\sum_{p\in C}\left\|\begin{pmatrix}\Pi p\\\
p^{\prime}\end{pmatrix}-\begin{pmatrix}\Pi c\\\
0\end{pmatrix}\right\|^{z}\leq(1+3\varepsilon)\textsc{P-cost}_{0}(C^{\prime})+\varepsilon\textsc{P-cost}_{0}(C^{\prime})$
$\displaystyle\leq(1+O(\varepsilon))\textsc{P-cost}_{0}(C^{\prime}).$ (8)

The proof of the other direction is similar in spirit, but quite more
technical. For ease of reading, we defer it to the Appendix and lemma B.1. ∎

Combining with the existence of small partition coresets, the previous lemma
concludes the proof of theorem 4.1. Essentially, it is enough to compute the
set $\mathcal{N}$ and apply lemma 4.4 on a extension partition coreset of $P$,
which has therefore size independent of $n$. Due to the presence of
extensions, the proof requires a bit of technical attention.

###### Proof of Theorem 4.1.

The cost preserving sketch for $P$ is constructed as follows. First, use
theorem 3.1 to compute an $(\varepsilon,k,z)$-extension partition coreset
$\Omega$ of $P$, with extension $\Omega^{\prime}$, in time $k^{\log\log
k+\varepsilon^{-O(z)}}\cdot\text{poly}(nd)$. Let $g$ be the corresponding
mapping from $P$ to $\Omega$ (as in definition 2.3).

To apply lemma 4.4 on $\Omega$, we start by computing the set $\mathcal{N}$
given in the statement, for the set $\Omega$, in time
$|\Omega|^{O(\varepsilon^{-2})}=k^{\varepsilon^{-O(z)}}$. The size of
$\mathcal{N}$ is as well $k^{\varepsilon^{-O(z)}}$. We the use the algorithm
from theorem 2.7 to deterministically compute a linear mapping
$\Pi:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}$ with
$m\in\varepsilon^{-O(z)}\log k$ such that pairwise distances between points of
$\mathcal{N}$ are preserved, up to a distortion factor $(1\pm\varepsilon/z)$.
This can be done in time $O\left(n\cdot d\cdot
k^{\varepsilon^{O(-z)}}\cdot\log^{O(1)}n\right)$.

Now, lemma 4.4 ensures that for the extension $\Omega^{\prime}$ of $\Omega$
(where each point $p$ has coordinate extension $p^{\prime}$), and for any for
any subset $C$ of $\Omega$ (with extension $C^{\prime}$),

$\displaystyle\sum_{p\in C}\left\|\begin{pmatrix}\Pi p\\\
p^{\prime}\end{pmatrix}-\mu^{z}_{0}(\Pi^{\prime}(C))\right\|^{z}=(1\pm\varepsilon)\sum_{p\in
C}\left\|\begin{pmatrix}p\\\
p^{\prime}\end{pmatrix}-\mu^{z}_{0}(C^{\prime})\right\|^{z},$ (9)

where $\Pi^{\prime}(C):=\left\\{\begin{pmatrix}\Pi p\\\
p^{\prime}\end{pmatrix},p\in C\right\\}$ is the projection of $C$ with the
same extensions as $C^{\prime}$.

We define our cost preserving sketch for $P$ as follows: for any $p\in P$, let
$f(p):=\begin{pmatrix}\Pi g(p)\\\ g(p)^{\prime}\end{pmatrix}$, where
$g(p)^{\prime}$ is the extension of $g(p)$ in $\Omega^{\prime}$. Let
$\mathcal{C}=\left\\{C_{1},...,C_{k}\right\\}$ be a clustering of $P$. We will
show that
$\textsc{cost}(f(P),f(\mathcal{C}))=(1\pm\varepsilon)\textsc{cost}(P,\mathcal{C})$,
which will conclude.

For any cluster $C_{i}$, we denote $g(C_{i})$ the multiset $\left\\{g(p):p\in
C_{i}\right\\}$, and $g(C_{i})^{\prime}$ the extension
$\left\\{\begin{pmatrix}g(p)\\\ g(p)^{\prime}\end{pmatrix}:p\in
C_{i}\right\\}$.

$\displaystyle\textsc{P-cost}_{0}(f(P),f(\mathcal{C}))$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k}\textsc{cost}(f(C_{i}),\mu^{z}_{0}(f(C_{i})))$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{k}\sum_{p\in
C_{i}}\left\|\begin{pmatrix}\Pi g(p)\\\
g(p)^{\prime}\end{pmatrix}-\mu^{z}_{0}(\Pi^{\prime}(g(C_{i})))\right\|^{z}$
(using eq. 9) $\displaystyle\leq$
$\displaystyle(1+\varepsilon)\sum_{i=1}^{k}\sum_{p\in
C_{i}}\left\|\begin{pmatrix}g(p)\\\
g(p)^{\prime}\end{pmatrix}-\mu^{z}_{0}(g(C_{i})^{\prime})\right\|^{z}$
$\displaystyle\text{(by def. of }\mu^{z}_{0})$ $\displaystyle\leq$
$\displaystyle(1+\varepsilon)\sum_{i=1}^{k}\sum_{p\in
C_{i}}\left\|\begin{pmatrix}g(p)\\\
g(p)^{\prime}\end{pmatrix}-\begin{pmatrix}\mu^{z}(C_{i})\\\
0\end{pmatrix}\right\|^{z}$ (by prop. of $g$) $\displaystyle\leq$
$\displaystyle(1+\varepsilon)^{2}\sum_{i=1}^{k}\sum_{p\in
C_{i}}\|p-\mu^{z}(C_{i})\|^{z}$ $\displaystyle=$
$\displaystyle(1+\varepsilon)^{2}\textsc{P-cost}(P,\mathcal{C}).$

We proceed similarly for the other direction: let $s_{i}$ such that
$\begin{pmatrix}s_{i}\\\ 0\end{pmatrix}=\mu_{0}^{z}(g(C_{i})^{\prime})$

$\displaystyle\textsc{P-cost}(P,\mathcal{C})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k}\sum_{p\in
C_{i}}\left\|p-\mu^{z}(C_{i})\right\|^{z}$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{k}\sum_{p\in C_{i}}\left\|p-s_{i}\right\|^{z}$ (by
prop. of $g$) $\displaystyle\leq$
$\displaystyle(1+\varepsilon)\sum_{i=1}^{k}\sum_{p\in
C_{i}}\left\|\begin{pmatrix}g(p)\\\
g(p)^{\prime}\end{pmatrix}-\mu_{0}^{z}(g(C_{i})^{\prime})\right\|^{z}$ (using
eq. 9) $\displaystyle\leq$
$\displaystyle(1+\varepsilon)^{2}\sum_{i=1}^{k}\sum_{p\in
C_{i}}\left\|\begin{pmatrix}\Pi g(p)\\\
g(p)^{\prime}\end{pmatrix}-\mu^{z}_{0}(\Pi^{\prime}(g(C_{i})))\right\|^{z}$
$\displaystyle=$
$\displaystyle(1+\varepsilon)^{2}\sum_{i=1}^{k}\textsc{cost}(f(C_{i}),\mu^{z}_{0}(f(C_{i})))$
$\displaystyle=$
$\displaystyle(1+\varepsilon)^{2}\textsc{P-cost}_{p}(f(P),f(\mathcal{C}))$

Hence, $\textsc{P-cost}_{0}(f(P),f(\mathcal{C}))\in(1\pm
O(\varepsilon))\textsc{P-cost}(P,\mathcal{C})$: $f$ is indeed a cost
preserving sketch for $P$, with target dimension $m+1=\varepsilon^{-O(z)}\log
k$, which concludes the proof.

In the particular case where $z\in\\{1,2\\}$, then the size of the partition
coreset is essentially $k^{\varepsilon^{-z-6}}$: therefore, the size of
$\mathcal{N}$ is $k^{\varepsilon^{-z-8}}$, and the target dimension of the
embedding is $\varepsilon^{-z-10}\log k$. ∎

######  Remark 4.5.

If allowing randomization, one can compute an arbitrary JL embedding onto
$\log k\varepsilon^{-O(z)}$ dimensions: with good probability, this will
preserves distances between points of $\mathcal{N}$ defined in lemma 4.4, and
therefore the proof of Theorem 4.1 goes through with this embedding. In
particular, one could use the sparse-JL constructions of [KN14] to get a
faster running time in case of sparse inputs.

##  5 Improved Deterministic Coreset Construction via Uniform VC-dimension

We focus in this section on a different notion of compression, namely
coresets. As mentionned in the introduction, our construction works in general
metric spaces, and not simply in Euclidean Spaces. In the following, we will
work in a metric space $(X,\text{dist})$: we will show a general coreset
construction, as well as a tailored version of it to Euclidean Spaces.

Recall the definition of a coreset definition 2.4: an
$(\varepsilon,k,z)$-coreset with offset for the $(k,z)$-Clustering problem for
$P$ is a set $\Omega$ with weights $w:\Omega\rightarrow\mathds{R}_{+}$
together with a constant $F$ such that, for any set $\mathcal{S}\subset X$,
$|\mathcal{S}|=k$,

$\textsc{cost}^{z}(\Omega,\mathcal{S})+F=(1\pm\varepsilon)\textsc{cost}^{z}(P,\mathcal{S})$

We will heavily rely on notions from VC-dimension literature, defined as
follows:

######  Definition 5.1.

A tuple $(X,\mathcal{R})$ is a _range space_ when
$\mathcal{R}=(R_{1},...,R_{m})$ with $R_{i}\subseteq X$.

A set $A$ is an $\varepsilon$-set-approximation555this is usually simply
called an $\varepsilon^{\prime}$-approximation, but we already use this
terminology for the cost of solutions. for $(X,\mathcal{R})$ if

$\forall R\in\mathcal{R},\left|\frac{|R|}{|X|}-\frac{|R\cap
A|}{|A|}\right|\leq\varepsilon.$

The VC-dimension of a range space is the size of the largest set $Y$ such that
$\\{Y\cap R,~{}R\in\mathcal{R}\\}=2^{|Y|}$, meaning that every subset of $Y$
is of the form $Y\cap R$ for some $R\in\mathcal{R}$.

The main result of the section is the following theorem. We relate the size of
the coreset to the VC dimension of the range space $\mathcal{B}$ formed by $k$
balls, defined as follows: For a point $c\in X$ and $r\in\mathbb{R}_{\geq 0}$,
let $H_{c,r}=\\{p\in P~{}|~{}\text{dist}(p,c)\geq r\\}$. For $k$ centers
$C=\\{c_{1},c_{2},\ldots,c_{k}\\}$, we similarly define $H_{C,r}=\\{p\in
P~{}|~{}\min_{c\in C}\text{dist}(p,c)\geq r\\}$. We let
$\mathcal{B}:=\bigcup_{C}\bigcup_{r}H_{C,r}$.

######  Theorem 5.2.

Let $(X,\text{dist})$ be a metric space such that the VC dimension of
$(P,\mathcal{B})$ is $D$. There exists a deterministic algorithm running in
deterministic time $\tilde{O}(|X|\cdot|P|\cdot
k/\varepsilon)+k\left(D/\varepsilon\right)^{O(D)}\cdot|P|$ that constructs an
$\varepsilon$-coreset with offset for the set $P$, with size $2^{O(z\log
z)}\cdot\frac{kD\log(D)\text{polylog}(1/\varepsilon)}{\varepsilon^{5}}$.

In the Euclidean Space $\mathds{R}^{d}$, the running time is $k^{\log\log
k+\varepsilon^{-O(z)}}\cdot\text{poly}(|P|d)+k\left(D/\varepsilon\right)^{O(D)}\cdot|P|$.

The exponential term in $D$ comes from the computation of $\varepsilon$-set
approximations: if allowing for randomization, this can be done merely by
uniform sampling. In that case, the complexity becomes simply
$\tilde{O}\left(|X|\cdot|P|\cdot k/\varepsilon\right)$.

###  5.1 Application to Euclidean Spaces via Dimension Reduction, and Proof of
theorem 1.5.

Our prominent example is the Euclidean case. It is well known from the coreset
literature that the set system aforementioned has VC-dimension $O(kd\log k)$
in Euclidean spaces of dimension $d$. This has been proven for example Lemma 1
of [BLHK17] and Corollary 34 of [FSS20] 666The bounds in the literature are
often stated for a generalization known as the weighted function space induced
by $k$-clustering in Euclidean spaces, which is necessary for coreset
constructions based on importance sampling. Here, we show how to use uniform
sampling instead, which allows us to use theorem 5.4 as a black box.. This in
particular leads to $\varepsilon^{\prime}$-set-approximation of size
$O\left(\frac{kd\log k}{\varepsilon^{\prime 2}}\cdot\log(kd\log
k/\varepsilon^{\prime})\right)$.

In order to remove the dependency in $d$ and match the best coreset result, we
aim at using a classical terminal embedding to reduce the dimension. In
particular, we will start from the extension-coreset of size
$k^{\varepsilon^{-O(z)}}$ from theorem 3.1, and apply a deterministic terminal
embedding construction on it. Since the pre-image of a coreset computed after
a terminal embedding is a coreset in the original space (see [HV20] or
[CSS21]), this yields the following corollary:

######  Corollary 5.3.

Given a set of $n$ point $P\subset\mathds{R}^{d}$, there exist a deterministic
algorithm running in time $k^{\log\log
k+\varepsilon^{-O(z)}}\cdot\text{poly}(nd)+\exp\left(\varepsilon^{-O(z)}k\log^{3}k\right)$
that constructs a set $\Omega\subseteq\mathds{R}^{d+1}$ of size
$k^{2}\log^{2}k\cdot\varepsilon^{-O(z)}$ together with a constant $F$ such
that:

$\forall\mathcal{S}\in(\mathds{R}^{d})^{k},\textsc{cost}(\Omega,\mathcal{S}^{\prime})+F=(1\pm\varepsilon)\textsc{cost}(P,\mathcal{S}),$

where $\mathcal{S}^{\prime}$ is the zero extension of $\mathcal{S}$, namely,
$\mathcal{S}^{\prime}=\left\\{\begin{pmatrix}s\\\
0\end{pmatrix},s\in\mathcal{S}\right\\}$.

###### Proof.

To reduce the dimension, we use our extension-partition coreset construction
combined with a terminal embedding, as for instance in Huang and Vishnoi
[HV20].

We start by computing a $(\varepsilon,k,z)$-extension partition coreset
$\Omega_{1}$ of $P$ of size $k^{\varepsilon^{-O(z)}}$, using theorem 3.1, in
time $k^{\log\log k+\varepsilon^{-O(z)}}\cdot\text{poly}(nd)$.

In particular, we have for any solution $\mathcal{S}\in(\mathds{R}^{d})^{k}$
with zero-extension $\mathcal{S}^{\prime}$

$\textsc{cost}(\Omega_{1},\mathcal{S}^{\prime})=(1\pm\varepsilon)\textsc{cost}(P,\mathcal{S})$
(10)

Now, we compute a terminal-embedding $\Pi$ of $\Omega_{1}$ onto
$\varepsilon^{-O(z)}\log k$ dimensions. Using the techniques from [HV20], any
coreset of $\Pi(\Omega_{1})$ after projection is a coreset of $\Omega_{1}$.

The terminal embedding can be done deterministically in time
$k^{\varepsilon^{-O(z)}}$ using the algorithm from [MMMR18] combined with
theorem 2.7.

Now, we can compute a coreset of the embedding using theorem 5.2. Since in
dimension $O(\varepsilon^{-O(z)}\log k)$ the VC-dimension of
$(\Pi(\Omega_{1}),\mathcal{B})$ is at most $\varepsilon^{-O(z)}k\log^{2}k$,
this is done deterministically in time $k^{\log\log
k+\varepsilon^{-O(z)}}\cdot\text{poly}(nd)+\exp\left(\varepsilon^{-O(z)}k\log^{3}k\right)$.
The pre-image $\Omega$ of that coreset is, by the techniques of Huang and
Vishnoi, a coreset for $\Omega_{1}$ in $\mathds{R}^{d+1}$. Therefore, we have:

$\textsc{cost}(\Omega,\mathcal{S}^{\prime})+F=(1\pm\varepsilon)\textsc{cost}(\Omega_{1},\mathcal{S}^{\prime})$
(11)

Combining eq. 10 and eq. 11 concludes the proof. ∎

A direct application of that corollary allows to compute a
$(1+\varepsilon)$-approximation to $(k,z)$-clustering in deterministic FPT
time, and proves our main theorem 1.5.

###### Proof of theorem 1.5.

The algorithm is simply the following: compute the dimension reduction of
theorem 4.1 onto dimension $d^{\prime}$, then the coreset $\Omega$ provided by
5.3, enumerate all possible $k$ clustering of it, keep the best one and
compute the center in $\mathds{R}^{d}$ associated with this clustering.

That way, we compute the optimal solution for $\Omega$ in
$\mathds{R}^{d^{\prime}+1}$ that has all its last coordinates equal to $0$,
$\mathcal{S}^{\prime}$. Let $\mathcal{S}$ be the corresponding solution in
$\mathds{R}^{d^{\prime}}$. Furthermore, let OPT be the optimal solution for
$P$, with zero-extension $\text{OPT}^{\prime}$. We have:

$\displaystyle(1-\varepsilon)\textsc{cost}(P,\mathcal{S})$
$\displaystyle\leq\textsc{cost}(\Omega,\mathcal{S}^{\prime})+F$
$\displaystyle\leq\textsc{cost}(\Omega,\text{OPT}^{\prime})+F$
$\displaystyle\leq(1+\varepsilon)\textsc{cost}(P,\text{OPT})$

Hence,
$\textsc{cost}(P,\mathcal{S})\leq\frac{1+\varepsilon}{1-\varepsilon}\textsc{cost}(P,\text{OPT})$,
and $\mathcal{S}$ is indeed a $(1+O(\varepsilon))$-approximation.

To enumerate all possible $k$ clustering, we use the algorithm of [IKI94] who
showed that for a set of $m$ points in $\mathds{R}^{d^{\prime}}$ there are
only $n^{O(kd^{\prime})}$ many possible clustering – and provided an efficient
way of doing so.

The running time is therefore: $k^{\log\log
k+\varepsilon^{-O(z)}}\cdot\text{poly}(nd)+\exp\left(\varepsilon^{-O(z)}k\log^{3}k\right)$
to compute $\Omega$, $|\Omega|^{k\log(k)\varepsilon^{-O(z)}}$ to enumerate all
$k$ clustering of $\Omega$ using [IKI94], and then
$\text{poly}(kd^{\prime}/\varepsilon)=\text{poly}(k/\varepsilon)$ to compute
the cost of each solution. Finally, the running time to compute the optimal
clusters in $\mathds{R}^{d}$ given the optimal partition in
$\mathds{R}^{d^{\prime}}$ is $\text{poly}(nd)$. Hence, in total, the running
time is

$k^{\log\log
k+\varepsilon^{-O(z)}}\cdot\text{poly}(nd)+2^{k\log^{3}k\cdot\varepsilon^{-O(z)}},$

which concludes. ∎

###  5.2 Application to Minor-Excluded Graphs, Graphs with Bounded Treewidth,
and Clustering of Curves.

Besides Euclidean spaces, theorem 5.2 can be applied to metrics for which the
VC-dimension of balls is bounded. In that way, it improves over the recent
result [BCJ+22], by saving a factor $k$ in the construction of coreset via
uniform sampling, and allowing deterministic implementations.

One such class of metric spaces is the ones induced by graphs excluding a
minor $H$: in that case, Bousquet and Thomassé [BT15] showed that the VC-
dimension of $(P,\mathcal{B})$ is $O(|H|k\log k)$.777Formally, they show the
result for $k=1$. [BFLR19] showed that extending the result to any $k$ looses
a $k\log k$ factor. Hence applying directly theorem 5.2 yields a coreset of
size $\tilde{O}\left(\frac{k^{2}|H|\log^{2}k}{\varepsilon^{5}}\right)$. The
construction is simplified compared to [CSS21], at the price of losing a
factor $k\varepsilon^{-1}$ (or $\varepsilon^{-3}$). On the other hand, the
dependency in the size of the minor is greatly improved: it is not even
specified precisely in [CSS21], although it seems to be at least doubly
exponential. This also improve over the
$\tilde{O}\left(|H|\text{poly}(k/\varepsilon)\right)$ of [BCJ+22], by
polynomial factors.

Since graphs with treewidth $t$ exclude the complete graph with $t$ vertices,
the result allows to construct coreset of size
$\tilde{O}\left(\frac{k^{2}t\log^{2}k}{\varepsilon^{5}}\right)$ for those –
which needs to be compared with the randomized bound
$\tilde{O}\left(kt\cdot\min\left(\varepsilon^{-2}+\varepsilon^{-z},\varepsilon^{-2}k\right)\right)$
of [CSS21]. As we will see, the running time is dominated by the construction
of an $\varepsilon$-set-approximation. Giving up on the determinism, this can
be made fast using random sampling (see Chazelle [Cha01]): this yields a
running time $\tilde{O}(|X|\cdot|P|\cdot k/\varepsilon)$. Again, the
construction is greatly simplified compared to [CSS21], to the price of a a
slightly worse coreset size.

##### Clustering of Curves.

Driemel, Nusser, Phillips, and Psarros showed in [DNPP21] VC dimension bounds
for clustering of curves, under the Fréchet and Hausdorff distances. The input
of that problem is a set of curves, each consisting of $m$ segments in
$\mathds{R}^{d}$, and the centers are restricted to be curves consisting of
$\ell$ segments in $\mathds{R}^{d}$.

They consider two types of distances for curves: the Hausdorff distance
between two curves $X$ and $Y$ is defined as follows: let
$d_{\vec{H}}(X,Y)=sup_{x\in X}\inf_{y\in Y}\|x-y\|$. The Hausforff distance
between $X$ and $Y$ is $\max(d_{\vec{H}}(X,Y),d_{\vec{H}}(Y,X))$. The Fréchet
distance is slightly more intricate: for that, we consider parametrized
curves, namely a curve is a function $X:[0,1]\rightarrow\mathds{R}^{d}$ whose
graph is made of $\ell$ consecutive segments. The Fréchet distance between two
parametrized curves $X$ and $Y$ is defined as
$\min_{f:[0,1]\rightarrow[0,1]}\max_{t\in[0,1]}\|X(f(t))-Y(t)\|$, where the
function $f$ is restricted to be continuous, non decreasing and with
$f(0)=0,f(1)=1$.

For both those distances, Driemel, Nusser, Phillips and Psarros [DNPP21]
showed that the VC dimension of $(P,\mathcal{B})$ is bounded by
$O\left(kd^{2}\ell^{2}\log(d\ell m)\log k\right)$. Hence, theorem 5.2 shows
the existence of a coreset of size $\frac{k^{2}d^{2}\ell^{2}\log(d\ell
m)\log^{2}k}{\varepsilon^{O(1)}}$. This improves over [BR21] and [BCJ+22],
although our construction is not polynomial time in that case.

###  5.3 A Sketch of the Construction

As explained in the introduction (section 1.3), our construction is inspired
by the one of Chen [Che09] and of [CSS21]. As both of those result, we start
by computing a constant-factor approximation, and placing rings of exponential
radius around each of its center.

We first use a careful preprocessing step to reduce the number of such rings
from $O(k\log n)$ as in [Che09] to $O(k)$. For this, we use a particularly
structured constant-factor approximation, that allows us to simply discard the
outer rings.

To build coresets in the remaining rings, both [Che09] and [CSS21] use uniform
sampling. Instead, we show that building an $\varepsilon^{\prime}$-set-
approximation of the set system formed by $k$ balls is actually enough: this
is doable deterministically, which concludes our algorithm.

The size of an $\varepsilon^{\prime}$-set-approximation can be bounded via the
VC-dimension of the set system:

######  Theorem 5.4 (Theorem 4.5 in Chazelle [Cha01]).

Let $(X,\mathcal{R})$ be a range space of VC-dimension $d$. Given any $r>0$,
an $r$-set-approximation for $(X,\mathcal{R})$ of size
$O\left(dr^{-2}\log(d/r)\right)$ can be computed deterministically in time
$d^{O(d)}\left(r^{-2}\log(d/r)\right)^{d}|X|$.

######  Theorem 5.5 (Theorem 4.9 in Chazelle [Cha01]).

Let $(X,\mathcal{R})$ be a range space of VC-dimension $d$. Given any $r>0$, a
uniform sample of size $O\left(r^{-2}(d\log(dr)+\log(1/\delta))\right)$ is a
$r$-set-approximation for $(X,\mathcal{R})$ with probability $1-\delta$.

We will compute $\varepsilon$-set-approximation for the set system
$(P,\mathcal{B})$, where $P$ is the set of input points and $\mathcal{B}$ is
defined in the opening paragraph.

###  5.4 The algorithm

As sketched, the algorithm partitions the input points into rings, and
computes then $\varepsilon$-set-approximation in each ring. We state here some
useful definitions.

Fix a metric space $(X,\text{dist})$, positive integers $k,z$ and a set of
clients $P$. For a solution $\mathcal{S}$ of $(k,z)$-clustering on $P$ and a
center $c\in\mathcal{S}$, $c$’s cluster consists of all points closer to $c$
than to any other center of $\mathcal{S}$. Note that this is different from
the dimension reduction setting of section 4, where the assignment are not
necessarily towards the closest center.

Fix as well some $\varepsilon>0$, and let $\mathcal{A}$ be any solution for
$(k,z)$-clustering on $P$ with $k$ centers. Let $C_{1},...,C_{k}$ be the
clusters induced by the centers of $\mathcal{A}$.

  * •

the average cost of a cluster $C_{i}$ is
$\Delta_{C_{i}}=\frac{\textsc{cost}(C_{i},\mathcal{A})}{|C_{i}|}$

  * •

For all $i,j$, the ring $R_{i,j}$ is the set of points $p\in C_{i}$ such that

$2^{j}\Delta_{C_{i}}\leq\textsc{cost}(p,\mathcal{A})\leq
2^{j+1}\Delta_{C_{i}}.$

  * •

The inner ring $R_{I}(C_{i})$ (resp. outer ring $R_{O}(C_{i})$) of a cluster
$C_{i}$ consists of the points of $C_{i}$ with cost at most
$\left(\nicefrac{{\varepsilon}}{{z}}\right)^{z}\Delta_{C_{i}}$ (resp. at least
$\left(\nicefrac{{z}}{{\varepsilon}}\right)^{2z}\Delta_{C_{i}}$), i.e.,
$R_{I}(C_{i}):=\cup_{j\leq z\log(\varepsilon/z)}R_{i,j}$ and
$R_{O}(C_{i}):=\cup_{j>2z\log(z/\varepsilon)}R_{i,j}$. The main ring
$R_{M}(C_{i})$ consists of all the other points of $C_{i}$. For a solution
$\mathcal{S}$, we let $R_{I}^{\mathcal{S}}$ and $R_{O}^{\mathcal{S}}$ be the
union of inner and outer rings of the clusters induced by $\mathcal{S}$.

The final algorithm is as follows:

Input: A metric space $(X,\text{dist})$, a set $P\subseteq X$, $k,z>0$,
$\varepsilon$ such that $0<\varepsilon<1/3$, and
$\varepsilon^{\prime}\leq\varepsilon$.
Output: A coreset with offset. Namely, a set of points $P^{\prime}\subseteq
X$, a weight function $w:P^{\prime}\mapsto\mathds{R}_{+}$ and an offset value
$F$ such that for any set of $k$ centers $C$,
$\textsc{cost}(P,C)=(1\pm\varepsilon)\textsc{cost}(P^{\prime},C)+F$.

  1. 1.

Greedy seeding:

    1. (a)

Compute a $c_{\mathcal{A}}$-approx $\mathcal{A}$ to the $(k,z)$-clustering
problem for $P$.888Any solution with $O(k)$ clusters and cost $O(\text{OPT})$
can be actually used for this step, in order to have a faster algorithm.

    2. (b)

Initialize $\mathcal{G}:=\mathcal{A}$.

    3. (c)

While:
$\textsc{cost}(\mathcal{G})\geq\varepsilon\textsc{cost}(\mathcal{A})/c_{\mathcal{A}}$
and there is a candidate center $c$ such that
$\left(1-\frac{\varepsilon}{k\cdot
c_{\mathcal{A}}}\right)\textsc{cost}(\mathcal{G})\geq\textsc{cost}(\mathcal{G}\cup\\{c\\})$
do:
$\mathcal{G}\leftarrow\mathcal{G}\cup\\{c\\}$.

  2. 2.

If
$\textsc{cost}(\mathcal{G})\leq\varepsilon\textsc{cost}(\mathcal{A})/c_{\mathcal{A}}$,
then output the following coreset and stop: $\mathcal{G}$ and
$w:\mathcal{G}\mapsto\mathds{R}_{+}$ where $w(c)$ corresponds to the number of
points served by center $c$ in $\mathcal{G}$, and offset $F=0$.

  3. 3.

Let $F:=\textsc{cost}(R_{O}(\mathcal{G}),\mathcal{G})$ be the cost of the
outer points of $\mathcal{G}$.

  4. 4.

Set the weights of all the centers of $\mathcal{G}$ to 0.

  5. 5.

Reducing the number of rings::
For each cluster $C$ with center $c$ of $\mathcal{G}$, remove all the points
in $R_{I}(C)\cup R_{O}(C)$ and increase the weight of $c$ by the number of
removed points. Let $I_{G}$ be the instance created with those weights.

  6. 6.

Sampling from the remaining rings: For every cluster $C_{i}$, and every $j$ ,
compute an $\varepsilon^{\prime}$-set-approximation $\Omega_{i,j}$ of the set
system $(R_{i,j},\mathcal{B})$. Weight the points of $\Omega_{i,j}$ by
$\frac{R_{i,j}}{|\Omega_{i,j}|}$.

  7. 7.

Output:

     * •

An instance $I_{G}$ created at Step 5

     * •

A coreset consisting of $\mathcal{G}\cup\Omega_{i,j}$, with offset $F$ defined
at Step 3 and weights for $\mathcal{G}$ defined throughout the algorithm,
weights for $\Omega_{i,j}$ defined by the sampling procedure.

If the condition
$\textsc{cost}(\mathcal{G})\leq\varepsilon\textsc{cost}(\mathcal{A})/c_{\mathcal{A}}$
is met, then we say that $\mathcal{G}$ is _low-cost_ ; otherwise, we say it is
_locally stable_.

We will need to compare cost of solution in the original instance $I$, and in
the one computed by the algorithm: cost will denote the cost in $I$ while
$\textsc{cost}_{I_{G}}$ the one for instance $I_{G}$.

###  5.5 Proof of the Greedy Seeding

The outcome of the greedy seeding step, $I_{G}$, satisfies the following
lemma:

######  Lemma 5.6.

Suppose $\mathcal{G}$ is locally stable. Let
$F=\sum\limits_{C\in\mathcal{G}}\sum\limits_{p\in
R_{O}(C)}\textsc{cost}(p,\mathcal{G})$ be the cost of points in outer rings.
For every solution $\mathcal{S}$, it holds that

$|\textsc{cost}(\mathcal{S})-(\textsc{cost}_{I_{G}}(\mathcal{S})+F)|\leq\varepsilon\textsc{cost}(\mathcal{S}).$

Before proving lemma 5.6, we show that the solution $\mathcal{G}$ has the
following properties:

######  Lemma 5.7.

$\mathcal{G}$ contains at most $O(k\cdot
z\cdot\log(1/\varepsilon)/\varepsilon)$ centers and, in the case where
$\mathcal{G}$ is locally stable, for any solution $\mathcal{S}$ and any subset
$Q\subseteq P$,
$\textsc{cost}(Q,\mathcal{G})\leq\textsc{cost}(Q,\mathcal{S})+\varepsilon\text{OPT}$.

###### Proof.

Note that the cost of $\mathcal{G}$ is clearly at most the cost of
$\mathcal{A}$, whose cost is at most $c_{\mathcal{A}}$ times the cost of the
best solution for the $k$-clustering problem.

Each center added by the greedy step decreases its cost by a factor
$(1-\nicefrac{{\varepsilon}}{{c_{\mathcal{A}}k}})$, and the initial solution
$\mathcal{G}$ has cost $\textsc{cost}(\mathcal{G})$: since the algorithm stops
if the cost drops below
$\varepsilon\textsc{cost}(\mathcal{A})/c_{\mathcal{A}}$, the total number of
centers added is at most $c_{\mathcal{A}}k\log(1/\varepsilon)/\varepsilon$ The
total number of centers is therefore at most
$c_{\mathcal{A}}k\log(1/\varepsilon)/\varepsilon$.

Note also that $\textsc{cost}(\mathcal{A})/c_{\mathcal{A}}\leq\text{OPT}$:
hence, the inequality
$(1-\nicefrac{{\varepsilon}}{{c_{\mathcal{A}}k}})\textsc{cost}(\mathcal{G})\leq\textsc{cost}(\mathcal{G}\cup\\{c\\})$
implies
$\textsc{cost}(\mathcal{G})\leq\textsc{cost}(\mathcal{G}\cup\\{c\\})+\varepsilon\text{OPT}/k$.
Hence, since $\mathcal{G}$ is locally stable, there is no candidate center $c$
such that
$\textsc{cost}(\mathcal{G})-\textsc{cost}(\mathcal{G}\cup\\{c\\})\geq\varepsilon\text{OPT}/k$.
Let $\mathcal{S}$ be a solution, $Q$ be a subset of clients, $s$ be a center
of the solution $\mathcal{S}$ and $C_{s}$ be its cluster. Since the
improvement made by adding $s$ is at least $\sum_{p\in C_{s}\cap
Q}\textsc{cost}(p,\mathcal{G})-\textsc{cost}(p,\mathcal{S})$, it holds that
$\sum_{p\in C_{s}\cap
Q}\textsc{cost}(p,\mathcal{G})-\textsc{cost}(p,\mathcal{S})\leq\textsc{cost}(\mathcal{G})-\textsc{cost}(\mathcal{G}\cup\\{c\\})\leq\varepsilon\text{OPT}/k$.
Summing over the $k$ centers of the solution $\mathcal{S}$ yields the
inequality
$\textsc{cost}(Q,\mathcal{S})\leq\textsc{cost}(Q,\mathcal{G})+\varepsilon\text{OPT}$,
concluding the lemma. ∎

We can now turn to the proof of lemma 5.6, that shows that the the outer rings
of solution $\mathcal{G}$ can simply be discarded, and their cost added in the
offset $F$.

###### proof of lemma 5.6.

Fix a cluster $C$ of $\mathcal{G}$, with center $c$. We first want to show
that
$\textsc{cost}(C,\mathcal{S})\leq\textsc{cost}_{I_{G}}(C,\mathcal{S})+\textsc{cost}(R_{O}(C),\mathcal{G})+\varepsilon\textsc{cost}(C,\mathcal{S})$.
First, this is equivalent to
$\textsc{cost}(R_{O}(C),\mathcal{S})\leq|R_{O}(C)|\textsc{cost}(c,\mathcal{S})+\textsc{cost}(R_{O}(C),\mathcal{G})+\varepsilon\textsc{cost}(C,\mathcal{S})$,
as all points in $C\setminus R_{O}(C)$ have same cost in the original instance
and in $I_{G}$.

Using lemma 2.5, we have

$\textsc{cost}(R_{O}(C),\mathcal{S})\leq(1+\varepsilon)\textsc{cost}(R_{O}(C),\mathcal{G})+(1+z/\varepsilon)^{z-1}|R_{O}(C)|\textsc{cost}(c,\mathcal{S}).$

Hence, one needs to bound $|R_{O}(C)|\textsc{cost}(c,\mathcal{S})$. For that,
we show that the cost of clients in $R_{O}(C)$ can be charged to clients of
$R_{I}(C)\cup R_{M}(C)$.

First note by Markov’s inequality,
$|R_{O}(C)|\leq\left(\nicefrac{{\varepsilon}}{{z}}\right)^{2z}|C|$. Hence, one
can partition $R_{I}(C)\cup R_{M}(C)$ into parts of size at least
$s=(|C|-|R_{O}(C)|)/|R_{O}(C)|$, and assign every part to a point in
$R_{O}(C)$ in a one-to-one correspondence.

For such a point $p\in R_{O}(C)$ consider the $s$ points $p_{1},\ldots,p_{s}$
of the part assigned to it. We show how to charge
$\textsc{cost}(c,\mathcal{S})$ to the cost of those points. Let
$\mathcal{S}(p_{j})$ be the center serving $p_{j}$ in the solution
$\mathcal{S}$. It holds that
$\textsc{cost}(c,\mathcal{S})\leq\min_{j}\textsc{cost}(c,\mathcal{S}(p_{j}))$.
Averaging, this is at most
$\frac{1}{s}\sum_{j=1}^{s}\textsc{cost}(c,\mathcal{S}(p_{j}))$ which is due to
lemma 2.5 at most
$\frac{1}{s}\sum_{j=1}^{s}(1+\varepsilon)\textsc{cost}(p_{j},\mathcal{G})+(1+z/\varepsilon)^{z-1}\textsc{cost}(p_{j},\mathcal{S})$.
Since $1/s\leq
2|R_{O}(C)|/|C|=2\left(\nicefrac{{\varepsilon}}{{z}}\right)^{2z}$, we conclude
(using $2\left(\frac{\varepsilon}{z}\right)(1+\varepsilon)\leq 1$) that:

$\displaystyle|R_{O}(C)|\textsc{cost}(c,\mathcal{S})$ $\displaystyle\leq
2\left(\frac{\varepsilon}{z}\right)^{z+1}(1+\varepsilon)\sum_{p\in
R_{I}(C)\cup
R_{M}(C)}\textsc{cost}(p,\mathcal{G})+\textsc{cost}(p,\mathcal{S})$
$\displaystyle\leq\left(\frac{\varepsilon}{z}\right)^{z}(\textsc{cost}(C,\mathcal{G})+\textsc{cost}(C,\mathcal{S})).$
(12)

We apply this inequality to bound $\textsc{cost}(R_{O}(C),\mathcal{S})$:

$\displaystyle\textsc{cost}(R_{O}(C),\mathcal{S})$
$\displaystyle\leq(1+\varepsilon)\textsc{cost}(R_{O}(C),\mathcal{G})+(1+z/\varepsilon)^{z-1}|R_{O}(C)|\textsc{cost}(c,\mathcal{S})$
$\displaystyle\leq\textsc{cost}(R_{O}(C),\mathcal{G})+2\varepsilon(\textsc{cost}(C,\mathcal{G})+\textsc{cost}(C,\mathcal{S}))$

Hence, summed over all cluster, this yields

$\textsc{cost}(R_{O},\mathcal{S})\leq\textsc{cost}(R_{O},\mathcal{G})+2\varepsilon(\textsc{cost}(\mathcal{G})+\textsc{cost}(\mathcal{S}))$
(13)

We now turn to the other direction of the inequality. Using lemma 5.7,

$\displaystyle\textsc{cost}(R_{O},\mathcal{G})$
$\displaystyle\leq\textsc{cost}(R_{O},\mathcal{S})+\varepsilon\text{OPT}$
$\displaystyle\leq\textsc{cost}(R_{O},\mathcal{S})+\varepsilon\textsc{cost}(\mathcal{S})$

Combined with eq. 12, this yields

$\displaystyle\textsc{cost}(R_{O},\mathcal{G})+\textsc{cost}_{I_{G}}(R_{O},\mathcal{S})-\textsc{cost}(R_{O},\mathcal{S})\leq
2\varepsilon(\textsc{cost}(\mathcal{S})+\textsc{cost}(\mathcal{G})).$ (14)

Combining eq. 13 and eq. 14, and using that all points not in $R_{O}$ have
same cost in the original instance and in $I_{G}$ concludes the lemma. ∎

###  5.6 Computing Coresets via $\varepsilon$-set-approximation: Proof of
lemma 5.8

We first show that an $\varepsilon$-set-approximation of the set system
$(R_{i,j},\mathcal{B})$ is indeed a coreset for $R_{i,j}$. We will then bound
the size of such an approximation. In this section, we fix the cluster $C_{i}$
and a ring $R_{i,j}$.

######  Lemma 5.8.

Let $R_{i,j}$ be a ring, and $\Omega$ be an $\varepsilon^{\prime}$-set-
approximation for $(R_{i,j},\mathcal{B})$ with
$\varepsilon^{\prime}=20\frac{8^{z}\varepsilon^{2}}{\log(4z/\varepsilon)}$.
Then $\Omega$ with uniform weights $|R_{i,j}|/|\Omega|$ is an
$\varepsilon$-coreset for $R_{i,j}$.

We use the same proof technique as [CSS21] to analyze the algorithm. More
precisely, we define ranges of clients: we let $I_{i,j,\ell}$ to be the set of
points from $R_{i,j}$ that pays roughly $(1+\varepsilon^{\prime})^{\ell}$ is
$\mathcal{S}$, i.e., $I_{i,j,\ell}:=\\{p\in
R:(1+\varepsilon^{\prime\prime})^{\ell}\leq\textsc{cost}(p,\mathcal{S})<(1+\varepsilon^{\prime\prime})^{\ell+1}\\}$,
where $\varepsilon^{\prime\prime}$ will be set later.

This analysis distinguishes between three cases:

  1. 1.

$\ell\leq j+\log_{1+\varepsilon^{\prime\prime}}\varepsilon$, in which case we
say that $I_{\ell}$ is _tiny_. The union of all tiny ranges is denoted
$I_{tiny,\mathcal{S}}$.

  2. 2.

$j+\log_{1+\varepsilon^{\prime\prime}}\varepsilon\leq\ell\leq
j+\log_{1+\varepsilon^{\prime\prime}}(4z/\varepsilon)$, in which case we say
$I_{\ell}$ is _interesting_.

  3. 3.

$\ell\geq j+\log_{1+\varepsilon^{\prime\prime}}(4z/\varepsilon)$, in which
case we say $I_{\ell}$ is _huge_.

The very same proof as Lemma 5 and 7 of [CSS21] shows that the cost the tiny
and huge ranges are preserved. For completeness, we provide statement and
proofs in appendix C. For the interesting ranges, we use properties of
$\varepsilon^{\prime}$-set-approximation as follows.

######  Lemma 5.9.

Let $R_{i,j}$ be a ring, and $\mathcal{S}$ be a solution such that all huge
$I_{\ell}$ are empty. Further, let $\Omega$ be an $\varepsilon^{\prime}$-set-
approximation for $(R,\mathcal{B})$, and uniform weights $|R|/|\Omega|$ for
point in $\Omega$. Then, if $\varepsilon^{\prime\prime}=\varepsilon/10$ and
$\varepsilon^{\prime}=20\frac{2^{3z}\varepsilon^{2}}{\log(4z/\varepsilon)}$,
it holds that
$\textsc{cost}(\Omega,S)=(1\pm\varepsilon)\textsc{cost}(R_{i,j},S)$.

###### Proof.

Fix some solution $\mathcal{S}$. For simplicity, we drop the subscript $i,j$
and let $R:=R_{i,j},I_{\ell}:=I_{i,j,\ell}$.

To show that
$\textsc{cost}(\Omega,\mathcal{S})=(1\pm\varepsilon)\textsc{cost}(\mathcal{S})$,
we will show the following stronger property: for any $\ell$,

$|\textsc{cost}(I_{\ell},\mathcal{S})-\textsc{cost}(I_{\ell}\cap\Omega,\mathcal{S})|\leq\frac{\varepsilon}{\log(4z/\varepsilon)}\textsc{cost}(I_{\ell},\mathcal{S}).$

Hence, we fix some integer $\ell$. Note that
$I_{\ell}=H_{\mathcal{S},(1+\varepsilon^{\prime\prime})^{\ell+1}}\setminus
H_{\mathcal{S},(1+\varepsilon^{\prime\prime})^{\ell}}$, where
$H_{\mathcal{S},r}=\\{p\in P:\text{dist}(p,\mathcal{S})\geq
r\\}\in\mathcal{B}$. Since $\Omega$ is an $\varepsilon^{\prime}$-set-
approximation for $(P,\mathcal{B})$, it holds that

$\displaystyle\left|\frac{|H_{\mathcal{S},(1+\varepsilon^{\prime\prime})^{\ell+1}}|}{|R|}-\frac{|H_{\mathcal{S},(1+\varepsilon^{\prime\prime})^{\ell+1}}\cap\Omega|}{|\Omega|}\right|\leq\varepsilon^{\prime}$
$\displaystyle\left|\frac{|H_{\mathcal{S},(1+\varepsilon^{\prime\prime})^{\ell}}|}{|R|}-\frac{|H_{\mathcal{S},(1+\varepsilon^{\prime\prime})^{\ell}}\cap\Omega|}{|\Omega|}\right|\leq\varepsilon^{\prime}$

Combining those two guarantees with triangle inequality ensure that

$\displaystyle\left|\frac{|I_{\ell}|}{|R|}-\frac{|I_{\ell}\cap\Omega|}{|\Omega|}\right|$
$\displaystyle\leq\left|\frac{|H_{\mathcal{S},(1+\varepsilon^{\prime\prime})^{\ell+1}}|}{|R|}-\frac{|H_{\mathcal{S},(1+\varepsilon^{\prime\prime})^{\ell+1}}\cap\Omega|}{|\Omega|}\right|+\left|\frac{|H_{\mathcal{S},(1+\varepsilon^{\prime\prime})^{\ell}}|}{|R|}-\frac{|H_{\mathcal{S},(1+\varepsilon^{\prime\prime})^{\ell}}\cap\Omega|}{|\Omega|}\right|$
$\displaystyle\leq 2\varepsilon^{\prime}.$

Furthermore, by definition of $I_{\ell}$,
$|I_{\ell}|\cdot(1+\varepsilon^{\prime\prime})^{\ell}\leq\textsc{cost}(I_{\ell},\mathcal{S})<|I_{\ell}|\cdot(1+\varepsilon^{\prime\prime})^{\ell+1}$.
Similarly, due to the weighting of points in $\Omega$, we have
$(1+\varepsilon^{\prime\prime})^{\ell}\frac{|R|\cdot|I_{\ell}\cap
R|}{|\Omega|}\leq\textsc{cost}(I_{\ell}\cap\Omega,\mathcal{S})$ Combining
those equations, we get

$\displaystyle\textsc{cost}(I_{\ell},\mathcal{S})$
$\displaystyle\leq|I_{\ell}|\cdot(1+\varepsilon^{\prime\prime})^{\ell+1}$
$\displaystyle\leq|I_{\ell}\cap\Omega|\cdot(1+\varepsilon^{\prime\prime})^{\ell+1}\cdot\frac{|R|}{|\Omega|}+2\varepsilon^{\prime}\cdot|R|(1+\varepsilon^{\prime\prime})^{\ell+1}$
$\displaystyle\leq(1+\varepsilon^{\prime\prime})\textsc{cost}(I_{\ell}\cap\Omega,\mathcal{S})+2\varepsilon^{\prime}\cdot|R|(1+\varepsilon^{\prime\prime})^{\ell+1}.$

To bound further the right hand side, we let $q\in I_{\ell}$, so that
$(1+\varepsilon^{\prime\prime})^{\ell}\leq\textsc{cost}(q,\mathcal{S})$:

$\displaystyle|R|(1+\varepsilon^{\prime\prime})^{\ell}$
$\displaystyle\leq\sum_{p\in R}\textsc{cost}(q,\mathcal{S})\leq\sum_{p\in
R}2^{z-1}\textsc{cost}(p,q)+2^{z-1}\textsc{cost}(p,\mathcal{S})$
$\displaystyle\leq 2^{z-1}\textsc{cost}(R,\mathcal{S})+2^{z-1}\sum_{p\in
R}2^{z-1}\left(\textsc{cost}(p,\mathcal{G})+\textsc{cost}(q,\mathcal{G})\right)$
$\displaystyle\leq
2^{z}\textsc{cost}(R,\mathcal{S})+2^{3z-1}\textsc{cost}(R,\mathcal{G}),$

where the last line uses $\textsc{cost}(q,\mathcal{G})\leq
2^{z}\textsc{cost}(p,\mathcal{G})$, since $p$ and $q$ are in the same ring.

Combined with the previous inequality, this yields
$\textsc{cost}(I_{\ell},\mathcal{S})\leq(1+\varepsilon^{\prime\prime})\textsc{cost}(I_{\ell}\cap\Omega,\mathcal{S})+2^{3z}\varepsilon^{\prime}\cdot\left(\textsc{cost}(R,\mathcal{S})+\textsc{cost}(R,\mathcal{G})\right)$.

Similarly, we get

$\displaystyle\textsc{cost}(I_{\ell}\cap\Omega,\mathcal{S})\leq(1+\varepsilon^{\prime\prime})\textsc{cost}(I_{\ell},\mathcal{S})+2^{3z}\varepsilon^{\prime}(\textsc{cost}(R,\mathcal{S})+\textsc{cost}(R,\mathcal{G})).$

Summing that over the $\log_{1+\varepsilon^{\prime\prime}}(4z/\varepsilon)$
interesting ranges and combining with lemma C.1 gives that:

$\displaystyle|\textsc{cost}(I_{\ell},\mathcal{S})-\textsc{cost}(I_{\ell}\cap\Omega,\mathcal{S})|$
$\displaystyle\leq~{}$
$\displaystyle\log_{1+\varepsilon^{\prime\prime}}(4z/\varepsilon)\cdot
2^{3z}\varepsilon^{\prime}\cdot(\textsc{cost}(R,\mathcal{S})+\textsc{cost}(R,\mathcal{G}))+\varepsilon^{\prime\prime}\textsc{cost}(R\cap\Omega,\mathcal{S})+\varepsilon^{\prime\prime}\textsc{cost}(R,\mathcal{S}).$

Hence, we have:

$\displaystyle|\textsc{cost}(I_{\ell},\mathcal{S})-\textsc{cost}(I_{\ell}\cap\Omega,\mathcal{S})|$
$\displaystyle\leq\log_{1+\varepsilon^{\prime\prime}}(4z/\varepsilon)\cdot
2^{3z}\varepsilon^{\prime}\cdot(\textsc{cost}(R,\mathcal{S})+\textsc{cost}(R,\mathcal{G}))$
$\displaystyle~{}~{}+\varepsilon^{\prime\prime}\textsc{cost}(R\cap\Omega,\mathcal{S})+\varepsilon^{\prime\prime}\textsc{cost}(R,\mathcal{S})$
$\displaystyle\leq\log_{1+\varepsilon^{\prime\prime}}(4z/\varepsilon)\cdot
2^{3z}\varepsilon^{\prime}\cdot(\textsc{cost}(R,\mathcal{S})+\textsc{cost}(R,\mathcal{G}))$
$\displaystyle~{}~{}+2\varepsilon^{\prime\prime}\textsc{cost}(R,\mathcal{S})+\varepsilon^{\prime\prime}|\textsc{cost}(R,\mathcal{S})-\textsc{cost}(R\cap\Omega,\mathcal{S})|$
$\displaystyle\leq\left(\log_{1+\varepsilon^{\prime\prime}}(4z/\varepsilon)\cdot
2^{3z}\varepsilon^{\prime}+2\varepsilon^{\prime\prime}\right)\cdot(\textsc{cost}(R,\mathcal{S})+\textsc{cost}(R,\mathcal{G}))$
$\displaystyle~{}~{}+\varepsilon^{\prime\prime}|\textsc{cost}(R,\mathcal{S})-\textsc{cost}(R\cap\Omega,\mathcal{S})|,$

which is equivalent to

$|\textsc{cost}(R,\mathcal{S})-\textsc{cost}(R\cap\Omega,\mathcal{S})|\leq\frac{\log_{1+\varepsilon^{\prime\prime}}(4z/\varepsilon)\cdot
2^{3z}\varepsilon^{\prime}+2\varepsilon^{\prime\prime}}{(1-\varepsilon^{\prime\prime})}(\textsc{cost}(R,\mathcal{S})+\textsc{cost}(R,\mathcal{G}).$

Chosing $\varepsilon^{\prime\prime}$ such that
$\frac{2\varepsilon^{\prime\prime}}{1-\varepsilon^{\prime\prime}}\leq\frac{\varepsilon}{2}$
(e.g. $\varepsilon^{\prime\prime}=\varepsilon/10$) and $\varepsilon^{\prime}$
such that $\frac{\log_{1+\varepsilon^{\prime\prime}}(4z/\varepsilon)\cdot
2^{3z}\varepsilon^{\prime}}{1-\varepsilon^{\prime\prime}}\leq\frac{\varepsilon}{2}$
(e.g.
$\varepsilon^{\prime}=20\frac{2^{3z}\varepsilon^{2}}{\log(4z/\varepsilon)}$)
concludes the lemma. ∎

Combining the results for tiny, interesting and huge ranges concludes the
proof of lemma 5.8 and shows that $\Omega_{i,j}$ is an $\varepsilon$-coreset
of $R_{i,j}$. Combined with lemma 5.6, this concludes the coreset guarantee of
theorem 5.2. The size of the coreset for a given ring is $O\left(2^{O(z\log
z)}D\varepsilon^{-4}\log(D/\varepsilon)\right)$ from theorem 5.4, and there
are
$O\left(2^{O(z\log z)}k\varepsilon^{-1}\text{polylog}(1/\varepsilon)\right)$
many rings. Hence, the total size of the coreset constructed is
$O\left(2^{O(z\log z)}\cdot
kD\varepsilon^{-k}\log(D)\text{polylog}(1/\varepsilon)\right)$ It only remains
to bound the time complexity of the algorithm.

###  5.7 Complexity Analysis

Two steps dominate the running time of the algorithm: the greedy seeding, and
the computation of the $\varepsilon^{\prime}$-set-approximation. For the
latter, a direct combination of theorem 5.4 shows that all the
$\varepsilon^{\prime}$-set-approximation can be computed in time
$k(D/\varepsilon)^{-O(d)}\cdot|X|$.

Hence, it only remains to bound the running time of the greedy seeding.

In the discrete metric case, this is straightforward: each iteration costs
$O(|X|\cdot|P|)$, and there are $\tilde{O}(k/\varepsilon)$ many of them (see
lemma 5.7).

The Euclidean case requires more work, as it is not possible to enumerate over
all candidate center. To implement the greedy seeding, we first use theorem
4.1 to reduce the dimension to $\varepsilon^{-O(z)}\log k$. In this low-
dimensional space, lemma 6.3 shows how to implement the greedy seeding
algorithm in time $n\log nk^{\varepsilon^{-O(z)}}$.

If the solution computed is low cost in the projected space, it is as well
low-cost in the original space. Furthermore, theorem 4.1 ensures that any
locally stable solution in the projected space is also locally stable for the
original input, therefore our argument follows. Note that it would not be
possible to compute an arbitrary bicriteria solution, for instance using
theorem 2.6: this would not ensure the local stability. Hence, we crucially
need to apply the dimension reduction from theorem 4.1, and not a terminal
embedding or a simpler dimension reduction. This concludes the proof of
theorem 5.2.

##  6 Deterministic Bicriteria Approximation

The goal of this section is to prove theorem 2.6, that we recall for
convenience: See 2.6

In order to compute a good solution efficiently, we rely on two results
allowing to reduce the dimension. We use a result from Makarychev, Makarychev
and Razenstein shows that their exist a dimension reduction onto
$O\left(\log(k/\varepsilon)/\varepsilon^{2}\right)$ that preserves the cost of
any clustering. A theorem from Kane and Nelson [KN14] allows to generate this
projection using few random bits: hence, we can enumerate over all realization
of those bits, compute the best solution in the projected space and lift it
back to the original one.

In the low dimensional space, we can compute an approximate solution using a
standard greedy procedure. For completeness, we provide proofs in section 6.1.
Before that, we state those two key theorems.

######  Theorem 6.1.

[Theorem 15 in Kane and Nelson] For any integer $d$ and any
$0<\varepsilon<1/2$, there exists an probability distribution on $d\times m$
random matrices such that for any $x\in\mathds{R}^{d}$ with $\|x\|=1$,

$\mathbb{P}_{\Pi}\left[\left|\|\Pi
x\|^{2}-1\right|\geq\varepsilon\right]\leq\exp(-\varepsilon^{2}m).$

Moreover, $\Pi$ can be sampled using $O\left(\varepsilon^{2}m\cdot\log
d\right)$ many random bits.

Given a seed and a vector $x\in\mathds{R}^{d}$, the embedding can be performed
in polynomial time.

######  Theorem 6.2.

[[MMR19]] The family of random maps defined in theorem 6.1 verifies, for
$m=O(\log(k/\varepsilon)/\varepsilon^{2})$ the following: for any set
$P\subseteq\mathds{R}^{d}$ and any partition $\mathcal{C}$ of $P$ into $k$
parts,

$\mathbb{P}_{\Pi}[\textsc{P-cost}\left(\Pi(P),\Pi(\mathcal{C})\right)=(1\pm\varepsilon)\textsc{P-cost}(P,\mathcal{C})]\geq
1/2$

###  6.1 Computing a Bicriteria Approximation in Low Dimensional Spaces

In this section, we show the following lemma:

######  Lemma 6.3.

There exists an algorithm running in time $n\log n(1/\varepsilon)^{O(d)}$ that
computes a set of $O(k\cdot\log(1/\varepsilon)/\varepsilon)$ many centers
$\mathcal{S}$, such that
$\textsc{cost}(P,\mathcal{S})\leq(1+\varepsilon)\text{OPT}$.

The algorithm is the standard bicriteria approximation. We provide proofs for
completeness: our contribution is presented in section 6.2.

  * •

Start computing an $\alpha$-approximation $S_{0}$ to $(k,z)$-clustering on
$A$.

  * •

As long as there exists a center $c$ such that
$\textsc{cost}(S_{i}\cup\\{c\\}\leq(1-\frac{\varepsilon}{\alpha
k})\textsc{cost}(S_{i})$, do $S_{i+1}\leftarrow S_{i}\cup\\{c\\}$ and
$i\leftarrow i+1$.

  * •

Stop this procedure when there is no such center $c$, or
$\textsc{cost}(S_{i})\leq\frac{\varepsilon}{\alpha}\textsc{cost}(S_{0})$, and
let $S$ be the final solution.

We break the proof of lemma 6.3 into two parts: first we show the quality of
the solution, and then how to implement fast the algorithm.

######  Lemma 6.4.

$\mathcal{S}$ is a
$\left((1+\varepsilon),\alpha\log(1/\varepsilon)/\varepsilon+1\right)$-bicriteria
approximation for $(k,z)$-clustering on $A$.

###### Proof.

Each center added decreases the cost by a factor
$(1-\nicefrac{{\varepsilon}}{{\alpha k}})$, and the initial solution $S_{0}$
has cost $\textsc{cost}(S_{0})$: since the algorithm stops if the cost drops
below $\varepsilon\textsc{cost}(S_{0})/\alpha$, the total number of centers
added is at most $\alpha k\log(1/\varepsilon)/\varepsilon$. The total number
of centers is therefore at most $\alpha k\log(1/\varepsilon)/\varepsilon+k$.

In the case where the procedure stops because
$\textsc{cost}(S)\leq\frac{\varepsilon}{\alpha}\textsc{cost}(S_{0})$, then $S$
has cost at most $\varepsilon$ times the optimal cost, since $S_{0}$ is an
$\alpha$-approximation. In that case, we are done.

In the other case, we note that $\textsc{cost}(S_{0})/\alpha\leq\text{OPT}$:
hence, the inequality $(1-\nicefrac{{\varepsilon}}{{\alpha
k}})\textsc{cost}(S)\geq\textsc{cost}(S\cup\\{c\\})$ implies
$\textsc{cost}(S)\geq\textsc{cost}(S\cup\\{c\\})+\varepsilon\text{OPT}/k$.
Hence, there is no candidate center $c$ such that
$\textsc{cost}(S)-\textsc{cost}(S\cup\\{c\\})\geq\varepsilon\text{OPT}/k$.
Summing over the $k$ centers of the optimal solution OPT yields the inequality
$\textsc{cost}(S)-\textsc{cost}(S\cup\text{OPT})\geq\varepsilon\text{OPT}$,
hence $S$ is a $(1+\varepsilon)$-approximation of OPT. This concludes the
lemma. ∎

It remains to show how to implement that greedy procedure fast. For that, we
discretize the set of candidate centers, to be able to check all of them.

For a point $p\in P$ and a radius $r$, we let $\mathbb{C}_{p,r}$ be an
$\frac{\varepsilon}{z}\cdot r$-cover of the ball $B(p,r)$. Given some
$\alpha$-approximation, we let $\Delta$ be the average cost of that solution.

We define $\mathbb{C}:=\cup_{p\in P}\cup_{i=\log(\varepsilon/(\alpha
z))}^{\log(n/\alpha)}\mathbb{C}_{p,2^{i/z}\Delta^{1/z}}$. We show that their
exists a near optimal solution with centers in $\mathbb{C}$:

######  Lemma 6.5.

There exists a solution $\mathcal{S}\in\mathbb{C}^{k}$ with cost
$(1+3\varepsilon)\text{OPT}$. Furthermore, $|\mathbb{C}|\leq n\log
n\cdot\varepsilon^{-O(d)}$ and can be computed in $O(|\mathbb{C}|)$ time.

###### Proof.

First, the size of $\mathbb{C}$ follows immediately from the size of covers in
$\mathds{R}^{d}$: there exists $\varepsilon$-covers of $B(0,1)$ of size
$\varepsilon^{-O(d)}$ that can be computed in time $\varepsilon^{-O(d)}$.

Given a cluster $C$ of the optimal solution, let $c^{*}$ be the optimal center
for $C$. We show there exist a good approximation $c$ to $c^{*}$ in
$\mathbb{C}$.

For this, let $p_{0}$ be the closest point in $C$ to $c^{*}$, and $i$ such
that $2^{(i-1)/z}\Delta^{1/z}\leq\text{dist}(p_{0},c^{*})\leq
2^{i/z}\Delta^{1/z}$.

First, if $i\leq\log(\varepsilon/(\alpha z))$, we let $c:=p_{0}$ so that
$\text{dist}(c,c^{*})\leq\frac{\varepsilon}{2\alpha z}\Delta$.

Hence, for any point $p\in C$, we have:

$\displaystyle|\textsc{cost}(p,c)-\textsc{cost}(p,c^{*})|$
$\displaystyle\leq\varepsilon\textsc{cost}(p,c^{*})+\left(\frac{\varepsilon+z}{\varepsilon}\right)^{z-1}\textsc{cost}(c,c^{*})$
$\displaystyle\leq\varepsilon\textsc{cost}(p,c^{*})+\left(\frac{\varepsilon+z}{\varepsilon}\right)^{z-1}\left(\frac{\varepsilon}{2\alpha
z}\right)^{z}\Delta$
$\displaystyle\leq\varepsilon\textsc{cost}(p,c^{*})+\varepsilon\Delta.$

In the other case, it must be that $i-1\leq\log(n/\alpha)$: otherwise,
$\text{OPT}\geq\textsc{cost}(p,c^{*})\geq 2^{i-1}\Delta\geq n\Delta/\alpha$,
and by definition of $\Delta$ we knew $n\Delta\leq\alpha\text{OPT}$, a
contradiction.

Let $c$ be the closest point to $c^{*}$ in $\mathbb{C}_{p_{0},i}$: by the
previous discussion, $c\in\mathbb{C}$ and the definition of
$\mathbb{C}_{p_{0},i}$ ensures that
$\text{dist}(c^{*},c)\leq\frac{\varepsilon}{4z}2^{i}\leq\frac{\varepsilon}{2z}\text{dist}(p_{0},c^{*})$.

Hence, for any point $p\in C$, we have just as before:

$\displaystyle|\textsc{cost}(p,c)-\textsc{cost}(p,c^{*})|$
$\displaystyle\leq\varepsilon\textsc{cost}(p,c^{*})+\left(\frac{\varepsilon+z}{\varepsilon}\right)^{z-1}\textsc{cost}(c,c^{*})$
$\displaystyle\leq\varepsilon\textsc{cost}(p,c^{*})+\left(\frac{\varepsilon+z}{\varepsilon}\right)^{z-1}\left(\frac{\varepsilon}{2z}\right)^{z}\textsc{cost}(p_{0},c^{*})$
$\displaystyle\leq 2\varepsilon\textsc{cost}(p,c^{*}).$

Summing over all points of $C$ gives
$\textsc{cost}(C,c)\leq(1+2\varepsilon)\textsc{cost}(C,c^{*})+\varepsilon/\alpha\cdot|C|\Delta$.
Summing now over all clusters and using $n\Delta\leq\alpha\text{OPT}$ ensures
that there is a solution with cost at most $(1+3\alpha)\text{OPT}$, with
center in $\mathbb{C}$. ∎

Hence, there exists a $(1+\varepsilon)$-approximation in $\mathbb{C}^{k}$.
Using this solution in place of the optimal one in the final equation of Lemma
6.4 ensures that the solution $\mathcal{S}$ given by the greedy algorithm
restricted to pick centers in $\mathbb{C}$ yields a
$(1+\varepsilon)$-approximation.

Using local-search (see e.g. Theorem 3.2 in [GT08]) for computing the
constant-factor approximation gives $\alpha=z^{O(z)}$: the solution
$\mathcal{S}$ is thus a
$(1+\varepsilon,z^{O(z)}\log(1/\varepsilon)/\varepsilon)$-bicriteria
approximation. For the running time, we use the fact that given one candidate
center, verifying whether adding it to the current solution decreases enough
the cost takes time $O(nd)$. Hence, the running time of this greedy bicriteria
algorithm is $n\log n\cdot\varepsilon^{-O(d)}\cdot
nd\log(1/\varepsilon)/\varepsilon$, which concludes the proof of lemma 6.3.

###  6.2 From High to Low dimension, and Vice-versa

Our first step is to reduce the dimension, in order to reduce the number of
random bits required by theorem 6.1.

For that, we use a result from [MMR19]: preserving pairwise distances between
the input points is enough to preserve the cost of any cluster. The proof is
based on Kirszbraun theorem, to find a Lipschitz extension of the function
mapping the projections of the input set to the original set. Using theorem
2.7, such a projection can be computed in deterministic polynomial time. It is
therefore enough to focus on a space of dimension
$\tilde{d}=O\left(\varepsilon^{-2}\log n\right)$.

Assuming now we are provided a
$\Pi:\mathds{R}^{\tilde{d}}\rightarrow\mathds{R}^{m}$ that verifies theorem
6.2, computing a good solution for $P$ boils down to computing one for
$\Pi(P)$ in $\mathds{R}^{m}$, with
$m=O\left(\varepsilon^{-2}\log(k/\varepsilon)\right)$. The algorithm from
lemma 6.3 gives a clustering with near-optimal cost in the low dimensional
space: to lift it in the original space, one can simply compute the optimal
center in $\mathds{R}^{d}$ for each cluster. This can be done using convex
programming in polynomial time.

To apply this idea, we enumerate over all possible seeds of bits of length

$O\left(\log\tilde{d}\cdot\log(\varepsilon^{-1}k)\right)=O\left(\log(\varepsilon^{-2}\log
n)\log(\varepsilon^{-1}k)\right).$

theorem 6.1 ensures that one of them will verify theorem 6.2. Our algorithm is
the following: given a seed, compute a near-optimal clustering in the
projected space. Then, compute the cost of that clustering in the original