# Moderate Dimension Reduction for $k$-Center Clustering

Shaofeng H.-C. Jiang
Peking University  Research partially supported by a national key R&D program
of China No. 2021YFA1000900 and a startup fund from Peking University. Email:
<EMAIL_ADDRESS>Robert Krauthgamer
Weizmann Institute of Science Work partially supported by the Israel Science
Foundation grant #1336/23 and the Weizmann Data Science Research Center.
Email<EMAIL_ADDRESS>Shay Sapir
Weizmann Institute of Science Partially supported by the Israeli Council for
Higher Education (CHE) via the Weizmann Data Science Research Center. Email:
<EMAIL_ADDRESS>
###### Abstract

The Johnson-Lindenstrauss (JL) Lemma introduced the concept of dimension
reduction via a random linear map, which has become a fundamental technique in
many computational settings. For a set of $n$ points in $\mathbb{R}^{d}$ and
any fixed $\epsilon>0$, it reduces the dimension $d$ to $O(\log n)$ while
preserving, with high probability, all the pairwise Euclidean distances within
factor $1+\epsilon$. Perhaps surprisingly, the target dimension can be lower
if one only wishes to preserve the optimal value of a certain problem, e.g.,
max-cut or $k$-means. However, for some notorious problems, like diameter (aka
furthest pair), dimension reduction via the JL map to below $O(\log n)$ does
not preserve the optimal value within factor $1+\epsilon$.

We propose to focus on another regime, of _moderate dimension reduction_ ,
where a problem’s value is preserved within factor $\alpha=O(1)$ (or even
larger) using target dimension $\log n/\mathrm{poly}(\alpha)$. We establish
the viability of this approach and show that the famous $k$-center problem is
$\alpha$-approximated when reducing to dimension $O(\tfrac{\log
n}{\alpha^{2}}+\log k)$. Along the way, we address the diameter problem via
the special case $k=1$. Our result extends to several important variants of
$k$-center (with outliers, capacities, or fairness constraints), and the bound
improves further with the input’s doubling dimension.

While our $\mathrm{poly}(\alpha)$-factor improvement in the dimension may seem
small, it actually has significant implications for streaming algorithms, and
easily yields an algorithm for $k$-center in dynamic geometric streams, that
achieves $O(\alpha)$-approximation using space
$\mathrm{poly}(kdn^{1/\alpha^{2}})$. This is the first algorithm to beat
$O(n)$ space in high dimension $d$, as all previous algorithms require space
at least $\exp(d)$. Furthermore, it extends to the $k$-center variants
mentioned above.

##  1 Introduction

The seminal work of Johnson and Lindenstrauss [JL84] introduced the technique
of dimension reduction via an (oblivious) random linear map, and this
technique has become fundamental in many computational settings, from offline
to streaming and distributed algorithms, especially nowadays that high-
dimensional data is ubiquitous. Their so-called JL Lemma asserts (roughly)
that for any fixed $\epsilon>0$, a random mapping (e.g., projection) of a set
$P\subset\mathbb{R}^{d}$ of $n$ points to target dimension $t=O(\log n)$
preserves the (Euclidean) distances between all points in $P$ within
$1+\epsilon$ factor. Furthermore, the JL Lemma is known to be tight [LN17],
see also the recent survey [Nel20].

Perhaps surprisingly, the target dimension can sometimes be reduced below that
$O(\log n)$ bound, particularly when one only wants to preserve the optimal
value of a specific objective function rather than all pairwise distances.
Indeed, for several optimization problems on the pointset $P$ (e.g., max-cut
and $k$-means), previous work has shown that the target dimension may be much
smaller than $O(\log n)$ or even independent of $n$ [LSS09, Lam10, BZD10,
CEM+15, BBC+19, MMR19, CW22, CJK23]. However, for some notorious problems,
like facility location, minimum spanning tree [NSIZ21] and diameter (aka
furthest pair), dimension reduction via the JL map to below $O(\log n)$ does
not preserve the optimal value within factor $1+\epsilon$.

In light of this, we consider a new regime of _moderate dimension reduction_ ,
where a problem’s value is approximated within factor $O(1)$ using target
dimension slightly below $O(\log n)$.111A related approach called low-quality
dimension reduction was proposed in [AEP18]. Similarly to ours, it refers to a
map with target dimension below $O(\log n)$ whose utility is to
$(1+\epsilon)$-approximate Nearest-Neighbor Search (NNS), but since NNS is not
an optimization problem, their definitions and techniques are rather different
from ours.  More precisely, we aim at a tradeoff of achieving
$O(\alpha)$-estimation,222 We say that dimension reduction achieves
$\alpha$-estimation if it preserves the problem’s optimal value within factor
$\alpha$; and we say it achieves $\alpha$-approximation if it also preserves
solutions, in a sense that we define formally later. Our results extend to
$O(\alpha)$-approximation, but we focus here on $O(\alpha)$-estimation for
clarity. for any desired $\alpha>1$, when reducing to dimension $\log
n/\operatorname{poly}(\alpha)$. This relaxation of the approximation factor,
from $1+\epsilon$ to $O(\alpha)$, may be effective in combating the “curse of
dimensionallity” phenomenon, because when an algorithm’s efficiency is
exponential in the dimension (e.g., space complexity in streaming algorithms),
bounds of the form $2^{O(\log n)}=n^{O(1)}$ improve to $2^{\log
n/\operatorname{poly}(\alpha)}=n^{1/\operatorname{poly}(\alpha)}$. This
tradeoff can even yield target dimension $t=O(1)$, by using a larger
approximation $\alpha=\operatorname{polylog}(n)$, and this can still lead to
new results (e.g., streaming algorithms).

We study this regime of moderate dimension reduction for the fundamental
problem of $k$-center clustering: The input is a set $P\subset\mathbb{R}^{d}$
of $n$ points, and the goal is to find a set of centers
$C\subset\mathbb{R}^{d}$ of size $k$ that minimizes the objective $\max_{p\in
P}\operatorname{dist}(p,C)$, where $\operatorname{dist}(p,C)=\min_{c\in
C}\|p-c\|$ (throughout, we use $\ell_{2}$ norm). Observe that the special case
$k=1$ is exactly the minimum enclosing ball problem (MEB), which is within
factor $2$ of the diameter problem, and for both problems, reducing the
dimension to $o(\log n)$ is unlikely to achieve $(1+\epsilon)$-estimation. We
design a general framework that works even for more challenging and widely
studied variants of $k$-center, such as the outliers [CCFM04], capacitated
[BKP93, KS00], and fair [CKLV17] variants.

###  1.1 Main Results

Our main result is a moderate dimension reduction for $k$-center via an
(oblivious) random linear map. For simplicity, let the map be defined via a
matrix $G\in\mathbb{R}^{d\times t}$ of iid Gaussians (scaled appropriately),
although our result is more general and holds for several (but not all) known
JL maps, similarly to prior work in this context [MMR19, CJK23]. Specifically,
we need $G$ to satisfy the JL Lemma and have a _sub-Gaussian tail_ , as
described in Section 1.4.

######  Theorem 1.1 (Main Result, informal).

For every $\alpha,d,k$ and $n$, suppose $G$ is as above with target dimension
$t=O(\frac{\log n}{\alpha^{2}}+\log k)$. Then, for every set
$P\subset\mathbb{R}^{d}$ of $n$ points, with high probability, $G$ preserves
the $k$-center value of $P$ within $O(\alpha)$ factor. This result extends to
$k$-center variants as listed in Table 1.

######  Remark 1.2.

We actually prove this theorem for target dimension
$t=O(\tfrac{d}{\alpha^{2}}+\log k)$, which is only stronger; indeed, one can
assume that $d=O(\log n)$ by the JL Lemma.

Table 1: Dimension reduction bounds for $O(\alpha)$-estimation of $k$-center variants, listed separately as a function of $n$ and of $d$.  $k$-center variant | target dimension | reference
---|---|---
vanilla | $O(\log n)$ | $d$ | JL Lemma/trivial
| $O(\frac{\log n}{\alpha^{2}}+\log k)$ | $O(\frac{d}{\alpha^{2}}+\log k)$ | Theorem 2.1
with $z$ outliers | $O(\log n)$ | $d$ | JL Lemma/trivial
| $O(\frac{\log n}{\alpha^{2}}+\log(kz))$ | $O(\frac{d}{\alpha^{2}}+\log(kz))$ | Theorem 3.1
assignment constrained | $O(\log n)$ | $d$ | JL Lemma/trivial
| $O(\frac{\log n}{\alpha}+\log k)$ | $O(\frac{d}{\alpha}+\log k)$ | Theorem 4.3

Our bound is nearly optimal when $G$ is a matrix of iid Gaussians (and
plausibly for all JL maps). Concretely, even for $k=1$, the target dimension
must be $t=\Omega(\tfrac{\log n}{\alpha^{2}})$, which matches the leading term
in our bound; and the second term is nearly matched by an $\Omega(\tfrac{\log
k}{\log\alpha})$ bound. For more details, see Appendix A.

To demonstrate that moderate dimension reduction is a general approach that
may be applied more broadly, our Theorem 1.1 includes non-trivial extensions
to several important variants of $k$-center. From here on, we call the classic
$k$-center mentioned above the “vanilla” variant, essentially to distinguish
it from other variants that we now discuss. In the variant _with outliers_
(aka robust $k$-center), the input specifies also $z\geq 0$, and the goal is
to find, in addition to the set of centers $C$, a set of at most $z$ outliers
$Z\subset P$, that minimizes the objective $\max_{p\in P\setminus
Z}\operatorname{dist}(p,C)$ [CCFM04]. Another variant, called $k$-center _with
an assignment constraint_ , asks to assign each input point to one of the $k$
clusters (not necessarily to the closest center), given a constraint on the
entire assignment, and the goal is to minimize the maximum cluster radius.
This formulation via a constrained assignment has been studied before for
other clustering problems [SSS19, HJV19, BFS21, BCJ+22] but not for
$k$-center. It is useful as a generalization that captures both the
capacitated variant, where every cluster has a bounded capacity [BKP93, KS00],
and the fair variant, where input points have colors and the relative
frequency of colors in every cluster must be similar to that of the entire
input [CKLV17]. Perhaps surprisingly, the dimension reduction satisfies a
strong “for all” guarantee with respect to the assignment constraints, i.e.,
with high probability the optimal value is preserved simultaneously for all
possible constraints (whose number can be extremely large). This is in
contrast to the weaker “for each” guarantee, where the high-probability bound
applies separately to each constraint. The extensions to $k$-center variants
come at the cost of a slightly increased target dimension, as listed in Table
1.

Another important feature of our approach is that it actually preserves
solutions, i.e., Theorem 1.1 extends from $O(\alpha)$-estimation to
$O(\alpha)$-approximation, as follows. For vanilla $k$-center, an _$\alpha$
-approximate solution_ of $P$ is a set $C\subset P$ of size $k$ whose
objective value $\max_{p\in P}\operatorname{dist}(p,C)$ is within factor
$\alpha$ from the optimal. The proof of Theorem 1.1 can be extended to show
that a set $C\subset P$ is an $O(\alpha)$-approximate solution of $P$ whenever
$G(C)$ is an $O(1)$-approximate solution of $G(P)$.333For a set
$X\subset\mathbb{R}^{d}$ and matrix $G\in\mathbb{R}^{t\times d}$, let
$G(X)\coloneqq\\{Gx\mathrel{\mathop{\ordinarycolon}}\ x\in X\\}$. The above
restriction to $C\subset P$ is needed to guarantee that $C\mapsto G(C)$ is
one-to-one, but one can easily relax it to our true requirement
$C\subset\mathbb{R}^{d}$ by introducing a factor of $2$ in the approximation
ratio. This extension to $O(\alpha)$-approximation holds also for the
aforementioned variants of $k$-center.

Still, an important question remains — how useful is this theorem, and more
generally, this regime of moderate dimension reduction? It may seem that for
fixed $\alpha>1$, the target dimension $\tfrac{\log
n}{\operatorname{poly}(\alpha)}=\Theta(\log n)$ offers only negligible
improvement over the JL Lemma. The crux is that many algorithms depend
exponentially in the dimension, in which case decreasing the dimension _by a
constant factor_ amounts to a _polynomial improvement_. We indeed show such an
application to streaming algorithms, as discussed next.

###  1.2 Application: Dynamic Geometric Streams

In dynamic geometric streams, a model introduced by Indyk [Ind04], the input
$P$ is presented as a stream of insertions and deletions of points from
$[\Delta]^{d}=\\{1,2,...,\Delta\\}^{d}$. Algorithms in this model read the
stream in one pass and their space complexity (aka storage requirement) is
limited. We assume that $\Delta\leq\operatorname{poly}(n)$, which is common in
this model. Ideally, algorithms for $k$-center should use at most
$\operatorname{poly}(kd\log n)$ bits of space, which is polynomial in the bit
representation of a solution consisting of $k$ points in $[\Delta]^{d}$. We
focus throughout on the general case of high dimension (say $d\geq\log n$),
and mostly ignore algorithms for the low-dimensional setting, as their space
complexity is not sublinear in $n$ for high dimension.

For $k$-center in insertion-only streams (i.e., without deletions), the
tradeoff between approximation and space complexity is well understood, and
the regime of $O(1)$-approximation seems to be the most useful and
interesting. Indeed, there is $O(1)$-approximation algorithm using $O(kd\log
n)$ bits of space [CCFM04], with extensions to the outliers variant [MK08] and
also to the sliding-window model [CSS16]. In contrast, all known
$(1+\epsilon)$-approximation algorithms have space bound that grows like
$(1/\epsilon)^{d}$ [AP02, CPP19, dBMZ21, dBBM23], which is not sublinear in
$n$ for high dimension. Furthermore, approximation below
$\tfrac{1+\sqrt{2}}{2}$ provably requires $\Omega(\min\\{n,\exp(d^{1/3})\\})$
bits of space, even for $k=1$ [AS15]. Another indication is a
$(1.8+\epsilon)$-approximation for vanilla $k$-center using space complexity
bigger by factor $k^{O(k)}$ [KA15].

The setting of dynamic streams (i.e., with deletions) seems much harder. Here,
$O(1)$-estimation using $\operatorname{poly}(kd\log n)$ bits of space is
widely open, as we seem to lack effective algorithmic techniques. For example,
in insertion-only streams, $2$-approximation can be easily achieved for $k=1$,
by just storing the first point (in the stream) and then the furthest point
from it. It is unknown whether this algorithm extends to dynamic streams,
because it relies on access to a point from $P$ right as the stream begins. We
provide an algorithm for dynamic streams and all $k$, by simply applying our
moderate dimension reduction result.

######  Theorem 1.3 (Streaming Algorithm for $k$-Center, informal).

There is a randomized algorithm that, given $\alpha,d,k,n$ and a set
$P\subset\mathbb{R}^{d}$ of size at most $n$ presented as a stream of
$\operatorname{poly}(n)$ insertions and deletions of points, returns an
$O(\alpha)$-approximation (value and solution) to the $k$-center problem on
$P$. The algorithm uses $n^{1/\alpha^{2}}\operatorname{poly}(kd\log n)$ bits
of space, and extends to $k$-center variants as listed in Table 2.

######  Remark 1.4.

This theorem can also achieve $2^{d/\alpha^{2}}\operatorname{poly}(kd\log n)$
bits of space, which is only stronger; indeed, one can assume that $d=O(\log
n)$ by the JL Lemma. By setting $\alpha$ appropriately, this algorithm
achieves $O(\sqrt{d/\log(kd\log n)})$-estimation using our ideal space bound
of $\operatorname{poly}(kd\log n)$ bits.

Table 2: Space complexity bounds for $O(\alpha)$-estimation in dynamic streams of $k$-center variants, listed separately as a function of $d$ and of $n$, but omitting $\operatorname{poly}(kd\log n)$ factors. The results of [dBBM23] actually achieve $(1+\epsilon)$-estimation.  $k$-center variant | space complexity of dynamic streaming | reference
---|---|---
vanilla | $2^{d}$ | - | [dBBM23]
| $2^{d/\alpha^{2}}$ | $n^{1/\alpha^{2}}$ | Corollary 2.3
with $z$ outliers | $z2^{d}$ | - | [dBBM23]
| $2^{d/\alpha^{2}}\operatorname{poly}(z)$ | $n^{1/\alpha^{2}}\operatorname{poly}(z)$ | Corollary 3.4
capacitated | $2^{d}$ | - | [dBBM23]
| $2^{d/\alpha}$ | $n^{1/\alpha}$ | Corollary 4.5
fair | $2^{d}$ | - | [dBBM23]
| $2^{d/\alpha}$ | $n^{1/\alpha}$ | Corollary 4.6

We do not know whether our bounds are tight, and in fact, proving lower bounds
for dynamic geometric streams is a challenging open problem (apparently, even
for deterministic algorithms). One would expect these lower bounds to exceed
those known for insertion-only streams, however, current techniques seem
unable to exploit deletions.

Our result improves and significantly generalizes the known bounds for
$k$-center in dynamic streams. Currently, the best algorithm that can handle
deletions works only for $k=1$ and the vanilla variant, and achieves
$O(\alpha)$-estimation using $\tilde{O}(n^{1/\alpha^{2}}d)$ bits of
space.444Throughout, the notation $\tilde{O}(f)$ hides
$\operatorname{poly}(\log n)$ factors. This result is unpublished but known to
experts, and follows by adapting a dynamic algorithm from [Ind03] to the
streaming setting. Known algorithms for insertion-only streams are largely not
relevant, as they rarely extend to handle deletions. Perhaps the only
exception is a simple approach based on $\epsilon$-nets (see e.g. [AP02]),
which was extended to handle deletions by employing sparse-recovery techniques
[dBBM23]. It was further extended to the outliers variant [dBBM23], and may
extend to the capacitated and fair variants as well. This algorithm achieves
$(1+\epsilon)$-approximation and uses space complexity that is bigger by
factor $(O(\frac{1}{\epsilon}))^{d}$, which unfortunately is not sublinear in
$n$ for high dimension. Another possible approach is to employ a recent
technique called consistent hashing [CFJ+22], to obtain (quite easily, details
omitted) a streaming algorithm for vanilla $k$-center that uses
$2^{d/\alpha}\operatorname{poly}(kd\log n)$ bits of space. The dependence on
$\alpha$ here is inferior to Theorem 1.3, and is known to be optimal for
consistent hashing [CFJ+22]. We remark that the tree-embedding technique of
[Ind04], which has been useful for several problems in high dimension, is
ineffective for $k$-center, or even the diameter problem, as it bounds only
the _expected stretch_ of every pair of points.

Recent research on streaming algorithms has uncovered an intriguing tradeoff
between approximation and space complexity for different geometric problems.
Interestingly, our tradeoff between approximation factor and space complexity
for vanilla $k$-center is better than the one known for these problems. For
earth mover’s distance (EMD) in the plane (i.e., $\mathbb{R}^{2}$), we know of
$O(\alpha)$-estimation using $\tilde{O}(n^{1/\alpha})$ bits of space
[ADIW09].555This result is in fact in terms of $\Delta$, but our assumption
$\Delta\leq\operatorname{poly}(n)$ implies
$\Delta^{O(1/\alpha)}=n^{O(1/\alpha)}$. For minimum spanning tree (MST), we
know of $O(\alpha)$-estimation using
$n^{\sqrt{\nicefrac{{\log\alpha}}{{\alpha}}}}\operatorname{poly}(d\log n)$
bits of space [CCJ+23]. For facility location, we know of
$O(\alpha)$-estimation using $n^{1/\alpha}\operatorname{poly}(d\log n)$ bits
of space [CFJ+22]. We currently have no satisfactory explanation for these
gaps, but since these four results rely on rather different methods,
developing unified techniques (possibly via dimension reduction) may
potentially improve some of these bounds.

###  1.3 Extension: Inputs of Small Doubling Dimension

When the input $P\subset\mathbb{R}^{d}$ has small doubling dimension, one can
achieve even better dimension reduction than Theorem 1.1, eliminating the
dependence (of $t$) on $d$ and $n$. Following [GKL03] (see also [Cla99]), the
_doubling dimension_ of a set $P\subset\mathbb{R}^{d}$, denoted
$\operatorname{ddim}(P)$, is the smallest number such that every ball (in $P$)
can be covered by $2^{\operatorname{ddim}(P)}$ balls of half the radius.
Dimension reduction for inputs of small doubling dimension has been studied
before for three problems: For facility location, one can achieve
$O(1)$-estimation using target dimension $t=O(\operatorname{ddim}(P))$
[NSIZ21]. For Nearest-Neighbour Search (NNS), one can obtain
$(1+\epsilon)$-approximation using
$t=O(\tfrac{\log(1/\epsilon)}{\epsilon^{2}}\operatorname{ddim}(P))$ [IN07],
and for minimum spanning tree (MST), one obtains $(1+\epsilon)$-estimation
using a similar target dimension albeit with another additive term of
$O(\tfrac{\log\log n}{\epsilon^{2}})$ [NSIZ21]. The following theorem, which
we prove in Section 5, shows an analogous result for $(1+\epsilon)$-estimation
of $k$-center.

######  Theorem 1.5 (Dimension Reduction for Doubling Sets, informal).

For every $\epsilon,d,k$ and $\operatorname{ddim}$, suppose $G$ is as in
Section 1.1 with target dimension
$t=O(\tfrac{\log(1/\epsilon)}{\epsilon^{2}}\operatorname{ddim}+\tfrac{\log
k}{\epsilon^{2}})$. Then, for every set $P\subset\mathbb{R}^{d}$ whose
doubling dimension is at most $\operatorname{ddim}$, with high probability,
$G$ preserves the $k$-center value of $P$ within $1+\epsilon$ factor.666The
$k$-center value here refers to $C\subset\mathbb{R}^{d}$, i.e., centers from
the ambient space. The theorem extends to preserving solutions, albeit with
the restriction $C\subseteq P$, which introduces a factor of $2$ in the
approximation.  This result extends to the $k$-center variants listed in Table
1.

Observe that by composing the maps in Theorems 1.1 and 1.5, we can achieve
$O(\alpha)$-approximation of $k$-center when reducing to target dimension
$t=O(\tfrac{\operatorname{ddim}(P)}{\alpha^{2}}+\log k)$. This bound is better
than the one in Theorem 1.1 since always $\operatorname{ddim}(P)=O(\min\\{\log
n,d\\})$. Consequently, the space of the streaming algorithm in Theorem 1.3
improves to $2^{\operatorname{ddim}(P)/\alpha^{2}}\operatorname{poly}(kd\log
n)$ bits. As the result extends to the $k$-center variants (with outliers and
with assignment constraint) in a natural way, we can replace $d$ with
$\operatorname{ddim}(P)$ also in Tables 1 and 2.

###  1.4 Technical Overview

We discuss below dimension reduction that maps from dimension $d$ to
$t=O(\frac{d}{\alpha^{2}}+\log k)$, and Theorem 1.1 follows by using the JL
Lemma to effectively assume $d=O(\log n)$, or alternatively by an easy
adaptation of the proof (essentially via Remark 1.7 below).

#### Warm Up: the Furthest Point Query Problem.

We start with the furthest point query (FPQ) problem, which may be of
independent interest, and admits the same dimension reduction as in Theorem
1.1, with a slightly simpler proof than for vanilla $k$-center (this proof is
provided formally in Appendix C). In this problem, the input is a _data set_
$P\subset\mathbb{R}^{d}$ of size $|P|=n$ and a _query set_
$Q\subset\mathbb{R}^{d}$ of size $|Q|\leq k$, and the goal is to report a
point from $P$ that is furthest from the set $Q$. Let $FPQ_{k}(P,Q)$ denote
this optimal value (distance from $Q$). One can use this problem to achieve
$2$-approximation for vanilla $k$-center, by simply employing the famous
Gonzalez’s algorithm (aka furthest-first traversal) [Gon85], which essentially
solves $k$ instances of FPQ.

We consider dimension reduction by a matrix of iid Gaussians, but actually,
all our results hold for any randomized map that satisfies (1) the JL Lemma
about distortion of distances, and (2) the following sub-Gaussian tail. We say
that a random map
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{d}\to\mathbb{R}^{t}$ has _sub-
Gaussian tail_ if

$\forall
x\in\mathbb{R}^{d},r>0,\qquad\Pr_{f}\big{[}\|f(x)\|\geq(1+r)\|x\|\big{]}\leq
e^{-\Omega(r^{2}t)}.$ (1)

This tail bound was key to prior work in this context, and it holds for a
$t\times d$ matrix of iid Gaussians $N(0,\tfrac{1}{t})$ [MMR19, CJK23]. Next
is a key lemma in our proof, which can be derived from [Ver18, Theorem 4.6.1]
for a matrix of independent sub-Gaussians, and we provide its proof in
Appendix B using only the JL Lemma and the sub-Gaussian tail property. Our
proof probably holds also for random projection (scaled appropriately), which
was used in [JL84, FM90].

######  Lemma 1.6.

Let $G\in\mathbb{R}^{t\times d}$ be a matrix of iid Gaussians $N(0,1)$, and
let $c_{0}>0$ be a suitable universal constant. Then

$\Pr\big{[}\sup_{\|x\|\leq 1}\|Gx\|>c_{0}\sqrt{d}\big{]}\leq 2^{-\Omega(d)}.$

######  Remark 1.7.

When restricting $x$ to be from a set $P\subset\mathbb{R}^{d}$, we can replace
$d$ with $\operatorname{ddim}(P)=O(\log n)$ by slightly adapting the proof,
thus w.h.p. $\|Gx\|\leq c_{0}\sqrt{\operatorname{ddim}(P)}$.

Our dimension-reduction map is defined via $\tfrac{1}{\sqrt{t}}G$ (for $G$ as
above), which is known to be a JL map [IM98, DG03]. If
$t\geq\tfrac{d}{\alpha^{2}}$, then by Lemma 1.6, with high probability, our
map expands all vectors at most by factor $O(\sqrt{d/t})=O(\alpha)$, thus the
value of $FPQ_{k}(P,Q)$ increases at most by this factor.

Consider a point $p^{*}\in P$ that is furthest from $Q$. If $t\geq c_{1}\log
k$ for a suitable constant $c_{1}>0$, then we can apply the JL Lemma (say,
with $\epsilon=\tfrac{1}{2}$) on $Q\cup\\{p^{*}\\}$ and get that with high
probability,
$\operatorname{dist}(\tfrac{1}{\sqrt{t}}Gp^{*},\tfrac{1}{\sqrt{t}}G(Q))\geq\tfrac{1}{2}\operatorname{dist}(p^{*},Q)$.
This concludes the proof for FPQ.

#### Framework for Problems with Small Witness.

An immediate corollary of Lemma 1.6 is that for every $k$-center variant, if
one uses target dimension $t\geq\tfrac{d}{\alpha^{2}}$, then the optimal value
increases at most by factor $O(\alpha)$. (Obviously, this fact may be useful
for many other geometric problems.) We denote by $\operatorname{opt}(X)$ the
optimal value of the problem at hand (e.g., vanilla or outliers) for a set
$X$.

It remains to prove that the optimal value does not decrease much, and we
devise for it the following approach: prove the existence of a small subset
$S\subset P$ (say, of size $O(k)$), that we shall call a _witness_ , for which
$\operatorname{opt}(S)=\Omega(\operatorname{opt}(P))$, and then apply the JL
Lemma on this set (say, with $\epsilon=\tfrac{1}{2}$). If $G$ preserves all
pairwise distances in $S$ up to factor $\tfrac{1}{2}$, then

$\operatorname{opt}(G(P))\geq\operatorname{opt}(G(S))\geq\tfrac{1}{2}\operatorname{opt}(S)=\Omega(\operatorname{opt}(P)),$

which concludes the proof. We apply this witness-based approach below, viewing
it as a framework that may find additional uses in the future.

#### Witness for Vanilla $k$-Center.

Consider running Gonzalez’s algorithm [Gon85], which is the following
iterative algorithm. Maintain a set $S\subseteq P$, initialized to contain one
arbitrary point from $P$, and then while $|S|\leq k$, find a solution for
$FPQ_{k}(P,S)$ (i.e., a point that is furthest from the current $S$) and add
it to $S$. It is well known that the distance between the last point added to
$S$ and the earlier points is in the range
$[\operatorname{opt}_{vanilla}(P),2\operatorname{opt}_{vanilla}(P)]$, and
moreover,
$\operatorname{opt}_{vanilla}(S)\geq\tfrac{1}{2}\operatorname{opt}_{vanilla}(P)$.
This set $S$ of size $k+1$ serves as our witness in Section 2.

#### Witness for $k$-Center with $z$ Outliers.

For this variant, we provide in Section 3 a witness of size $O(kz)$. The
construction is based on executing Gonzalez’s algorithm $z+1$ times, where
after each execution we delete from $P$ the $k+1$ points found in that
execution.

#### Assignment Constraint Variant.

We do not present a witness for this variant, and we bound the decrease in
value via a different method. We denote by
$\operatorname{opt}_{\mathcal{C}}(\cdot)$ the value of $k$-center with an
assignment constraint $\mathcal{C}$. Our proof in Section 4 compares
$\operatorname{opt}_{\mathcal{C}}$ to $\operatorname{opt}_{vanilla}$ (on the
same input $P$) — if these values are similar, then the proof is concluded by
the fact that $\operatorname{opt}_{vanilla}$ is preserved. Otherwise,
$\operatorname{opt}_{\mathcal{C}}$ is significantly larger than
$\operatorname{opt}_{vanilla}$, and for the sake of analysis, we “move” every
data point to its nearest “vanilla center”, thus we get a weighted set of $k$
points, where the total weight is $n$. The crux of the proof shows that under
the random linear map, moving points of $P$ corresponds to moving points of
$G(P)$, which in turn does not change $\operatorname{opt}_{\mathcal{C}}(G(P))$
by too much, essentially because by Lemma 1.6, points remain close to their
vanilla center.

#### Streaming Algorithm.

Our streaming algorithm is a corollary of the dimension reduction. First apply
the dimension reduction
$G\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{d}\to\mathbb{R}^{t}$ of Theorem
1.1 on every point in the input stream, and then employ a known algorithm
whose space is exponential in the reduced dimension $t$. The success
probability can be amplified by standard methods.

The known algorithm returns only an estimation, and not an approximate
solution, but this can be resolved, and even extended to return a solution in
$\mathbb{R}^{d}$ using existing techniques, as follows. We refer here to the
algorithm of [dBBM23] that computes a $(1+\epsilon)$-estimation (in
$\mathbb{R}^{t}$) using $\operatorname{poly}(k(1/\epsilon)^{t}\log n)$ bits of
space. It uses an $(\epsilon\operatorname{opt}_{vanilla})$-net and sparse
recovery, which allow it to find the non-empty net-points (viewed as buckets),
but these net-points need not correspond to points in $\mathbb{R}^{d}$. We
adapt this algorithm to report a solution (centers from $\mathbb{R}^{d}$,
actually from $P$) by using a two-level $\ell_{0}$-sampler [CFJ+22, Lemma
3.3], which can be viewed as a more sophisticated version of sparse recovery —
add to each insertion/deletion of a net-point (in $\mathbb{R}^{t}$) a “data
field” containing the original input point (in $\mathbb{R}^{d}$); now a two-
level sampler will pick a random net-point (bucket) and then a random element
from that bucket, with the element’s data field revealing an input point. This
method extends to the variants listed in Table 2, where throughout (i.e., for
all variants) a solution is defined to be just the set of $k$ centers.

###  1.5 Related Work

#### JL Maps.

There are other constructions of random linear maps that satisfy the JL Lemma
besides projection to a random subspace [JL84, FM90] and a matrix of Gaussians
[IM98, DG03], like a matrix of iid Rademacher random variables [Ach03] or
independent random variables with a sub-Gaussian tail (which includes both
Gaussians and Rademacher random variables) [Mat08, IN07, KM05]. Moreover,
there is a long line of work on maps with improved running time, e.g., the two
cornerstone results known as fast JL [AC06] and sparse JL [DKS10], although
these are not known to satisfy (1).

#### Streaming Algorithms in High Dimension.

For dynamic streams in high dimension, there is no prior work on $k$-center
(except for $k=1$, see Section 1.2), although there is work on other problems.
Ideal $(1+\epsilon)$-approximations are achieved for a few problems, including
clustering problems like $k$-means [HSYZ18] and $k$-median [BFL+17], where the
space bound is $\operatorname{poly}(\epsilon^{-1}kd\log\Delta)$, and more
recently for Max-Cut [CJK23]. For many other problems, existing algorithms
provide worse approximations, like $O(d\log\Delta)$ or $O(d)$ [Ind04, AIK08,
ADIW09, CJLW22, WY22, CFJ+22, CCJ+23]. In fact, some of the work mentioned
above (and also ours) provides a tradeoff between approximation and space
complexity (e.g., the space can vary between polynomial and exponential in
$d$), and it is open whether this tradeoff is necessary for these problems.

##  2 Dimension Reduction for Vanilla $k$-Center

In this section, we prove that a linear map via a matrix of iid Gaussians
preserves the vanilla $k$-center value and solution, hence prove the main
claim in Theorem 1.1.

######  Theorem 2.1.

Let $d,\alpha>1$ and $k\leq n$. There is a random linear map
$G\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{d}\to\mathbb{R}^{t}$ with
$t=O(\log k+\tfrac{d}{\alpha^{2}})$, such that for every set
$P\subset\mathbb{R}^{d}$ of size $n$, with probability at least $2/3$,

  * •

$\operatorname{opt}_{vanilla}(G(P))$ is an $O(\alpha)$-estimation for
$\operatorname{opt}_{vanilla}(P)$, and

  * •

$C\subset P$ is an $O(\alpha)$-approximate vanilla $k$-center solution of $P$
whenever $G(C)$ is an $O(1)$-approximate vanilla $k$-center solution of
$G(P)$.

In order to prove Theorem 2.1, we will use the following version of the JL
Lemma.

######  Fact 2.2 (JL Lemma [IM98, DG03]).

Let $G$ be a $t\times d$ matrix of iid Gaussians $N(0,1)$. Then

$\forall
x\in\mathbb{R}^{d}\enspace\text{and}\enspace\epsilon>0,\qquad\Pr\big{[}\tfrac{1}{\sqrt{t}}\|Gx\|\notin(1\pm\epsilon)\|x\|\big{]}\leq
2^{-\Omega(\epsilon^{2}t)}.$

###### Proof of Theorem 2.1..

Assume without loss of generality that the vanilla $k$-center value of $P$ is
$1$. Let $C^{*}\subset\mathbb{R}^{d}$ be a set of optimal centers, and let
$S\subset P$ be an output of Gonzalez’s algorithm after $k+1$ steps (i.e.,
$|S|=k+1$ and $\min_{s_{1},s_{2}\in S}\|s_{1}-s_{2}\|\geq 1$). We treat $S\cup
C^{*}$ as a _witness_ , as described in Section 1.4. Pick $T=\Theta(\sqrt{d})$
with a hidden constant that satisfies Lemma 1.6, set $\epsilon=\tfrac{1}{2}$,
and pick $t=O(\log k)+400\tfrac{T^{2}}{\alpha^{2}}$ such that the bound
$2^{-\Omega(t)}$ in 2.2 is at most $\tfrac{1}{10(2k+1)^{2}}$. Let $G$ be a
$t\times d$ matrix of iid Gaussians $N(0,1)$. Then, by 2.2 and a union bound,

$\Pr\big{[}\forall p_{1},p_{2}\in S\cup C^{*},\;\|G(p_{1}-p_{2})\|\in[1\pm
0.5]\sqrt{t}\|p_{1}-p_{2}\|\big{]}\geq
1-(2k+1)^{2}2^{-\Omega(t)}\geq\tfrac{9}{10}.$ (2)

By Lemma 1.6,

$\Pr\big{[}\forall x\in B(0,1),\;\|Gx\|\leq T\big{]}\geq 1-2^{-\Omega(d)}.$
(3)

Assuming the events in Equations 3 and 2 happen, the following holds.

#### Value.

For every set $C_{G}\subset\mathbb{R}^{t}$ of size $k$, we can restrict the
pointset to the set $S$,

$\displaystyle\max_{p\in P}\operatorname{dist}(Gp,C_{G})$
$\displaystyle\geq\max_{s\in S}\operatorname{dist}(Gs,C_{G})$ then use the
fact that $|S|=k+1$ and $|C_{G}|=k$,
$\displaystyle\geq\tfrac{1}{2}\min_{s_{1},s_{2}\in S}\|G(s_{1}-s_{2})\|$ and
now by the event in Equation 2 and by the choice of $S$,
$\displaystyle\geq\tfrac{\sqrt{t}}{4}\min_{s_{1},s_{2}\in
S}\|s_{1}-s_{2}\|\geq\tfrac{\sqrt{t}}{4}\geq\tfrac{T}{\alpha}.$

In the other direction, using the assumption, we have that for all $p\in P$,
$\operatorname{dist}(p,C^{*})\leq 1$, thus by the event in Equation 3,

$\displaystyle\min_{C_{G}\subset\mathbb{R}^{t},|C_{G}|=k}\max_{q\in
G(P)}\operatorname{dist}(q,C_{G})$ $\displaystyle\leq\max_{p\in
P}\operatorname{dist}(Gp,G(C^{*}))\leq T,$

which concludes the proof.

#### Solution.

We want to show that $C\subset P$ is an $O(\alpha)$-approximate $k$-center
solution of $P$ whenever $G(C)$ is a $2$-approximate $k$-center solution of
$G(P)$. We shall actually prove the contrapositive claim, and consider a set
$B\subset P$ for which there exists a point $p^{\prime}\in P$ such that
$\operatorname{dist}(p^{\prime},B)>5\alpha$. Now for every point $p\in P$,
denote by $c_{p}$ its closest center from $C^{*}$. Then the following holds.

$\displaystyle\operatorname{dist}(Gp^{\prime},G(B))$ $\displaystyle=\min_{b\in
B}\|G(p^{\prime}-b)\|$ by a triangle inequality, $\displaystyle\geq\min_{b\in
B}\|G(c_{p^{\prime}}-c_{b})\|-\|G(c_{p^{\prime}}-p^{\prime})\|-\|G(b-c_{b})\|$
by the event in Equation 3, $\displaystyle\geq\min_{b\in
B}\|G(c_{p^{\prime}}-c_{b})\|-2T$ by the event in Equation 2,
$\displaystyle\geq\min_{b\in
B}\tfrac{1}{2}\sqrt{t}\|c_{p^{\prime}}-c_{b}\|-2T$ by a triangle inequality,
$\displaystyle\geq\min_{b\in
B}\tfrac{1}{2}\sqrt{t}(\|p^{\prime}-b\|-\|c_{p^{\prime}}-p^{\prime}\|-\|b-c_{b}\|)-2T$
by assumptions, $\displaystyle\geq\tfrac{1}{2}\sqrt{t}5\alpha-\sqrt{t}-2T\geq
20T.$

Thus, $G(B)$ is not a $2$-approximate $k$-center solution of $G(P)$. This
concludes the proof of Theorem 2.1. The constant $2$ in the approximation is
arbitrary and could be changed to any other constant by adapting the other
parameters. ∎

A streaming algorithm now follows as an immediate corollary. Indeed, just
apply on the input the dimension reduction of Theorem 2.1, and then run a
known streaming algorithm for low dimensions (slightly adapted to report a
solution), as explained in Section 1.4.

######  Corollary 2.3 (Streaming Vanilla $k$-Center).

There is a randomized algorithm that, given as input numbers
$\alpha,k,n,d,\Delta$ and a set $P\subset[\Delta]^{d}$ of size at most $n$
presented as a stream of $\operatorname{poly}(n)$ insertions and deletions of
points, returns an $O(\alpha)$-approximation (value and solution) to
$k$-center on $P$. The algorithm uses
$\operatorname{poly}(k2^{d/\alpha^{2}}\log(n\Delta))$ bits of space and fails
w.p. at most $1/\operatorname{poly}(n)$.

##  3 Dimension Reduction for $k$-Center with Outliers

In this section, we design moderate dimension reduction for $k$-center with
$z$ outliers, and demonstrate its application to streaming algorithms. We
denote by $\operatorname{opt}_{outliers}(P)$ the optimal value of $k$-center
with $z$ outliers of $P$, and prove the following.

######  Theorem 3.1.

Let $k,z\leq n$ and $d,\alpha>1$. There is a random linear map
$G\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{d}\to\mathbb{R}^{t}$ with
$t=O(\tfrac{d}{\alpha^{2}}+\log(kz))$, such that for every set
$P\subset\mathbb{R}^{d}$ of size $n$, with probability at least $2/3$,

  * •

$\operatorname{opt}_{outliers}(G(P))\in\big{[}\operatorname{opt}_{outliers}(P),O(\alpha)\cdot\operatorname{opt}_{outliers}(P)\big{]}$,
and

  * •

$C,Z\subset P$ is an $O(\alpha)$-approximate solution of $k$-center with $z$
outliers of $P$ whenever $G(C),G(Z)$ is an $O(1)$-approximate solution of
$k$-center with $z$ outliers of $G(P)$.

We first show that every set $P\subset\mathbb{R}^{d}$ has a witness of size
$O(kz)$, i.e., a subset $P^{\prime}\subset P$ of size $|P^{\prime}|=O(kz)$,
such that
$\operatorname{opt}_{outliers}(P^{\prime})=\Omega(\operatorname{opt}_{outliers}(P))$.
The construction is based on executing Gonzalez’s algorithm $z+1$ times, each
execution without the previously chosen points. An important property of this
construction is that for every choice of $z$ outliers, one of the $z+1$
executions of Gonzalez’s algorithm returns a set of points without outliers.
Our analysis uses a specific choice of $z$ outliers that is optimized for
$P^{\prime}$.

######  Lemma 3.2 (Witness for the outliers variant).

For every $k,z$ and $P\subset\mathbb{R}^{d}$, there is a subset
$P^{\prime}\subset P$ of size $|P^{\prime}|=(k+1)(z+1)$, such that
$\operatorname{opt}_{outliers}(P^{\prime})\in[\tfrac{1}{3}\operatorname{opt}_{outliers}(P),\operatorname{opt}_{outliers}(P)]$.

######  Remark 3.3.

The size of this witness is tight up to low-order terms, by the following
example. Consider a set $X$ of $(k+1)z+1$ points, where there are $k+1$
locations with pairwise distances $1$, such that each location contains $z$
points, and the last remaining point is at distance $\tfrac{1}{3}$ from one of
these locations. Clearly, the cost of $k$-center with $z$ outliers is
$\tfrac{1}{6}$, by considering the $z$ points from one of the locations as
outliers. However, every strict subset of $X$ (i.e., excluding even one point)
has cost $0$, as there will be a location with $z-1$ points, which can be
taken as outliers, together with that last point.

###### Proof.

For a set $X$, we denote by $Gonz(X,k+1)$ a set of $k+1$ points computed by
executing Gonzalez’s algorithm (for $k$ iterations) on $X$, breaking ties like
the starting point arbitrarily. Given $P\subset\mathbb{R}^{d}$, construct a
witness for $k$-center with $z$ outliers as follows.

  1. 1.

$X\leftarrow P$

  2. 2.

for $i=1,\ldots,z+1$

  3. 3.

$C_{i}\leftarrow Gonz(X,k+1)$

  4. 4.

$X\leftarrow X\setminus C_{i}$

  5. 5.

return $P^{\prime}=\cup_{i\in[z+1]}C_{i}$ as a witness

Clearly,
$\operatorname{opt}_{outliers}(P^{\prime})\leq\operatorname{opt}_{outliers}(P)$.
It remains to prove that
$\operatorname{opt}_{outliers}(P^{\prime})\geq\tfrac{1}{3}\operatorname{opt}_{outliers}(P)$.

Let $C^{\prime}$ and $Z^{\prime}$ be the optimal centers and outliers for
$P^{\prime}$, respectively. Since $|Z^{\prime}|\leq z$, there exists
$i\in[z+1]$ such that $C_{i}\cap Z^{\prime}=\emptyset$. By the pigeonhole
principle, there are $p_{1},p_{2}\in C_{i}$ that are clustered to the same
cluster by $C^{\prime}$, and thus by a triangle inequality,
$\operatorname{dist}(p_{1},p_{2})\leq
2\operatorname{opt}_{outliers}(P^{\prime})$. Suppose without loss of
generality that $p_{1}$ was added to $C_{i}$ before $p_{2}$ in the execution
of Gonzalez’s algorithm. We can bound $\operatorname{opt}_{outliers}(P)$ by
considering centers $C^{\prime}$ and outliers $Z^{\prime}$, and thus

$\displaystyle\operatorname{opt}_{outliers}(P)$ $\displaystyle\leq\max_{p\in
P\setminus Z^{\prime}}\operatorname{dist}(p,C^{\prime})$
$\displaystyle=\max\\{\max_{p\in P\setminus
P^{\prime}}\operatorname{dist}(p,C^{\prime}),\max_{p\in P^{\prime}\setminus
Z^{\prime}}\operatorname{dist}(p,C^{\prime})\\}.$

The second term is by definition $\operatorname{opt}_{outliers}(P^{\prime})$,
so let us bound the first term. For every $p\in P\setminus P^{\prime}$, by the
triangle inequality,

$\operatorname{dist}(p,C^{\prime})\leq\min_{p^{\prime}\in
C_{i}}\\{\operatorname{dist}(p,p^{\prime})+\operatorname{dist}(p^{\prime},C^{\prime})\\}\leq\operatorname{dist}(p,C_{i})+\operatorname{opt}_{outliers}(P^{\prime}).$
(4)

Let $\hat{C}_{i}\subseteq C_{i}$ be the set $C_{i}$ _at the time that $p_{2}$
was chosen_ (in the $i$-th execution of Gonzalez’s algorithm). Then, because
$p\notin P^{\prime}$ is available at this time,

$\displaystyle\operatorname{dist}(p,C_{i})$
$\displaystyle\leq\operatorname{dist}(p,\hat{C}_{i})\leq\operatorname{dist}(p_{2},\hat{C}_{i})$
and since $p_{1}\in\hat{C}_{i}$,
$\displaystyle\leq\operatorname{dist}(p_{2},p_{1})\leq
2\operatorname{opt}_{outliers}(P^{\prime}).$

Together with (4), we obtain $\operatorname{dist}(p,C^{\prime})\leq
3\operatorname{opt}_{outliers}(P^{\prime})$, which concludes the proof. ∎

###### Proof of Theorem 3.1.

The proof that the value is preserved within factor $O(\alpha)$ using target
dimension $t=O(\tfrac{d}{\alpha^{2}}+\log(kz))$ is the same as the proof for
the vanilla variant, albeit with the witness given by Lemma 3.2. As for the
proof that solutions are preserved, it only requires few minor changes, as
follows.

Assume without loss of generality that $\operatorname{opt}_{outliers}(P)=1$.
Let $C^{*}$ and $Z^{*}$ be sets of optimal centers and outliers, respectively.
We can assume without loss of generality that the points in $Z^{*}$ are
furthest from $C^{*}$. Pick $t\geq b_{0}\log(kz)$, where $b_{0}>0$ is a fixed
constant such that by 2.2 and a union bound,

$\Pr\big{[}\forall p_{1},p_{2}\in P^{\prime}\cup C^{*}\cup
Z^{*},\;\|G(p_{1}-p_{2})\|\in[1\pm
0.5]\sqrt{t}\|p_{1}-p_{2}\|\big{]}\geq\tfrac{9}{10}.$ (5)

For every point $p\in P\setminus Z^{*}$, denote by $c_{p}$ its closest center
from $C^{*}$. We slightly abuse notation, and for every $p\in Z^{*}$ we denote
by $c_{p}$ the point $p$ itself. The proof proceeds by considering sets
$B\subset P$ of size $k$ and $Z^{\prime}\subset P$ of size $z$ for which there
exists a point $p^{\prime}\in P\setminus Z^{\prime}$ such that
$\operatorname{dist}(p^{\prime},B)>5\alpha$ and is the same as the proof of
Theorem 2.1. ∎

A streaming algorithm now follows as a corollary, using a known streaming
algorithm for low dimensions (slightly adapted to report a solution), as
explained in Section 1.4.

######  Corollary 3.4 (Streaming Algorithm for $k$-Center with $z$ Outliers).

There is a randomized algorithm that, given as input numbers
$\alpha,k,z,n,d,\Delta$ and set $P\subset[\Delta]^{d}$ of size at most $n$
presented as a stream of $\operatorname{poly}(n)$ insertions and deletions of
points, returns an $O(\alpha)$-approximation (value and solution) to
$k$-center with $z$ outliers on $P$. The algorithm uses
$\operatorname{poly}(kz2^{d/\alpha^{2}}\log(n\Delta))$ bits of space and fails
with probability at most $1/\operatorname{poly}(n)$.

##  4 Dimension Reduction for $k$-Center with an Assignment Constraint

In this section, we consider $k$-center with an assignment constraint, which
captures the capacitated and fair variants of $k$-center, as described in
Section 1.1. We design for this problem moderate dimension reduction, and
demonstrate its application to streaming algorithms. Our definition below of
an assignment constraint follows the one used in [SSS19, HJV19, BFS21, BCJ+22]
for other $k$-clustering problems. The _radius_ of a pointset is the optimal
value of $1$-center clustering for it.

######  Definition 4.1.

An _assignment_ is a map $\pi\mathrel{\mathop{\ordinarycolon}}[n]\to[k]$. An
_assignment constraint_ is a partition of all possible assignments into
feasible and infeasible ones, formalized as
$\mathcal{C}\mathrel{\mathop{\ordinarycolon}}[k]^{n}\to\\{0,1\\}$.

This definition can model clustering with capacity $L>0$, by declaring an
assignment $\pi$ to be feasible if $|\pi^{-1}(i)|\leq L$ for all $i\in[k]$. To
exemplify how it can model fair clustering, suppose the first $n/3$ points in
$P$ are colored blue and the others are red; then declare $\pi$ to be feasible
if exactly $1/3$ of the elements in every $\pi^{-1}(i)$ are from the range
$\\{1,\ldots,\frac{n}{3}\\}$. See Section 4.1 for more details.

######  Definition 4.2.

In _$k$ -center with an assignment constraint $\mathcal{C}$_, the input is a
set $P\subset\mathbb{R}^{d}$ of $n$ points, and the goal is to partition $P$
into $k$ sets (called clusters) in a manner feasible according to
$\mathcal{C}$ when viewed as an assignment,777To view a partition as an
assignment, represent $P$ by $[n]$ and the clusters by $[k]$, in an arbitrary
manner (not by the geometry of the points).  so as to minimize the maximum
cluster radius. The minimum value attained is denoted by
$\operatorname{opt}_{\mathcal{C}}(P)$. A _solution_ to this problem is a
partition of $P$ into $k$ sets, and is called _$\alpha$ -approximate_ if it is
feasible and has value at most
$\alpha\cdot\operatorname{opt}_{\mathcal{C}}(P)$.

The next theorem shows that reducing to dimension $O(\tfrac{d}{\alpha}+\log
k)$ preserves w.h.p. the value of $k$-center with an assignment constraint up
to an $O(\alpha)$ factor, simultaneously for all assignment constraints. Our
dimension bound here is worse by factor $\alpha$ compared to the vanilla
variant, essentially because our lower bound for the value of $G(P)$ is
weaker. More precisely, take as before $t=O(\tfrac{d}{\alpha^{2}}+\log k)$ and
let $G$ to be a matrix of iid Gaussians $N(0,\tfrac{1}{t})$. We show that
w.h.p., for all constraints $\mathcal{C}$ we have
$\tfrac{1}{\alpha}\operatorname{opt}_{\mathcal{C}}(P)\leq\operatorname{opt}_{\mathcal{C}}(G(P))\leq\alpha\operatorname{opt}_{\mathcal{C}}(P)$.
The upper bound here is as before, but the lower bound is weaker by factor
$\alpha$, hence we have to scale $G$ appropriately and substitute
$\alpha^{2}\to\alpha$ to conclude the theorem.

######  Theorem 4.3.

Let $d,\alpha>1$ and $k\leq n$. There is a random linear map
$G\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{d}\to\mathbb{R}^{t}$ with
$t=O(\tfrac{d}{\alpha}+\log k)$, such that for every set
$P\subset\mathbb{R}^{d}$ of size $n$, with probability at least $2/3$, the
following holds. For all
$\mathcal{C}\mathrel{\mathop{\ordinarycolon}}[k]^{n}\to\\{0,1\\}$,

  * •

$\operatorname{opt}_{\mathcal{C}}(G(P))\in\big{[}\operatorname{opt}_{\mathcal{C}}(P),O(\alpha)\cdot\operatorname{opt}_{\mathcal{C}}(P)\big{]}$,
and

  * •

a feasible partition of $P$ to $k$ clusters is an $O(\alpha)$-approximate
solution of $k$-center with assignment constraint $\mathcal{C}$ whenever the
corresponding partition of $G(P)$ is an $O(1)$-approximate solution of
$k$-center with assignment constraint $\mathcal{C}$ for $G(P)$.

Throughout this section, all sets are multisets. In order to prove Theorem
4.3, we will use the following lemma.

######  Lemma 4.4.

For every assignment constraint $\mathcal{C}$, and for every set $X$ of $n$
points, if one constructs a set $X^{\prime}$ by moving every point in $X$ by
distance at most $\Delta>0$, then
$\operatorname{opt}_{\mathcal{C}}(X^{\prime})\geq\operatorname{opt}_{\mathcal{C}}(X)-\Delta$.888This
movement-based lemma is symmetric — $X$ can be constructed by moving every
point in $X^{\prime}$ by distance at most $\Delta>0$, and thus
$\operatorname{opt}_{\mathcal{C}}(X)\geq\operatorname{opt}_{\mathcal{C}}(X^{\prime})-\Delta$.

###### Proof.

Immediate by considering the optimal solution for $X^{\prime}$, increasing the
radius by $\Delta$ and using the triangle inequality. ∎

###### Proof of Theorem 4.3.

Consider a matrix of Gaussians $G\in\mathbb{R}^{t\times d}$. Pick $t=O(\log
k+d/\alpha^{2})$ and $\epsilon=1/2$ such that the bound in 2.2 is
$2^{-\Omega(t)}\leq\tfrac{1}{10k^{2}}$ and such that by Lemma 1.6, w.h.p., all
vectors in $\mathbb{R}^{d}$ expand under $G$ by a factor of at most
$\tfrac{\alpha\sqrt{t}}{8}$.

The proof holds simultaneously for all assignment constraint $\mathcal{C}$,
since the success probability is only for (1) Lemma 1.6 and (2) JL for a set
of size $O(k)$ that is independent of $\mathcal{C}$. Both events are
independent of $\mathcal{C}$, and for the sake of analysis, we assume the
events are successful. By Lemma 1.6 and by considering the optimal solution
for $G(P)$,

$\operatorname{opt}_{\mathcal{C}}(\tfrac{4}{\sqrt{t}}G(P))\leq\tfrac{\alpha}{2}\operatorname{opt}_{\mathcal{C}}(P).$

We will show that
$\operatorname{opt}_{\mathcal{C}}(\tfrac{4}{\sqrt{t}}G(P))\geq\tfrac{1}{\alpha}\operatorname{opt}_{\mathcal{C}}(P)$.
Thus, $\operatorname{opt}_{\mathcal{C}}(\tfrac{4\alpha}{\sqrt{t}}G(P))$ is an
$\alpha^{2}$-approximation of $\operatorname{opt}_{\mathcal{C}}(P)$, and the
proof is concluded by substituting $\alpha^{2}\to\alpha$.

As in Section 2, by considering the output of Gonzalez’s algorithm after $k+1$
steps and by the JL lemma (2.2), with probability at least $8/10$,

$\displaystyle\operatorname{opt}_{vanilla}(\tfrac{4}{\sqrt{t}}G(P))\geq\operatorname{opt}_{vanilla}(P).$

Thus, if
$\operatorname{opt}_{\mathcal{C}}(P)\leq\alpha\operatorname{opt}_{vanilla}(P)$,
then

$\operatorname{opt}_{\mathcal{C}}(\tfrac{4}{\sqrt{t}}G(P))\geq\operatorname{opt}_{vanilla}(\tfrac{4}{\sqrt{t}}G(P))\geq\operatorname{opt}_{vanilla}(P)\geq\tfrac{1}{\alpha}\operatorname{opt}_{\mathcal{C}}(P).$

Hence, we assume from now on that
$\operatorname{opt}_{\mathcal{C}}(P)>\alpha\operatorname{opt}_{vanilla}(P)$.
Let $P^{\prime}$ be the set obtained by moving every point $p\in P$ to its
nearest center $c_{p}$ in the optimal vanilla $k$-center solution. It follows
that every point moves distance at most $\operatorname{opt}_{vanilla}(P)$.
Additionally, $G(P^{\prime})$ equals to the set obtained by moving every
projected point $Gp\in G(P)$ to its “projected center” $Gc_{p}$, and by Lemma
1.6, w.h.p. $\|Gp-
Gc_{p}\|\leq\tfrac{\alpha\sqrt{t}}{8}\|p-c_{p}\|\leq\tfrac{\alpha\sqrt{t}}{8}\operatorname{opt}_{vanilla}(P)$,
i.e., every point in $\tfrac{4}{\sqrt{t}}G(P)$ moves distance at most
$\tfrac{\alpha}{2}\operatorname{opt}_{vanilla}(P)$. Thus, by Lemma 4.4 for
$G(P)$ and $G(P^{\prime})$,

$\displaystyle\operatorname{opt}_{\mathcal{C}}(\tfrac{4}{\sqrt{t}}G(P))$
$\displaystyle\geq\operatorname{opt}_{\mathcal{C}}(\tfrac{4}{\sqrt{t}}G(P^{\prime}))-\tfrac{\alpha}{2}\operatorname{opt}_{vanilla}(P)$
and by applying the JL lemma (2.2) to $P^{\prime}$ that has at most $k$
distinct points, with probability at least $8/10$, $\displaystyle\geq
2\operatorname{opt}_{\mathcal{C}}(P^{\prime})-\tfrac{\alpha}{2}\operatorname{opt}_{vanilla}(P)$
and by Lemma 4.4 for $P$ and $P^{\prime}$, $\displaystyle\geq
2\big{(}\operatorname{opt}_{\mathcal{C}}(P)-\operatorname{opt}_{vanilla}(P)\big{)}-\tfrac{\alpha}{2}\operatorname{opt}_{vanilla}(P)$
and by our assumption above and since $\alpha\geq 2$,
$\displaystyle\geq\tfrac{1}{2}\operatorname{opt}_{\mathcal{C}}(P).$

This concludes the proof of the value estimation, and it immediate to see that
the value of an assignment is preserved similarly in this movement based
argument. ∎

###  4.1 Streaming Algorithms for Capacitated and Fair $k$-Center

There are streaming algorithms in low dimensions for both the capacitated and
fair variants of $k$-center using $k(1/\epsilon)^{d}\operatorname{poly}(\log
n)$ bits of space, similarly to what was done for the vanilla and outliers
variants by [dBBM23]. They consider an
$(\epsilon\operatorname{opt}_{vanilla})$-net, and using $\ell_{0}$-samplers,
they can find the non-empty net points (buckets), along with the number of
data points in each bucket. The proof proceeds by noting that the net argument
is “movement-based”, which respects capacities (in a trivial manner) and is
also known to work for fairness constraints [SSS19] (although the focus of
[SSS19] was on $k$-clustering and not on $k$-center). Thus, as corollaries of
Theorem 4.3, we get streaming algorithms for the capacitated and fair
variants.

#### Capacitated $k$-Center.

This variant, introduced by [BKP93], is a special case of $k$-center with an
assignment constraint. The input is a set $P\subset\mathbb{R}^{d}$ of $n$
points and a maximum load $L\leq n$, and the assignment constraint is that no
cluster has more than $L$ points.

######  Corollary 4.5.

There is a randomized algorithm that, given as input $\alpha>1,L,k,n,d,\Delta$
and set $P\subset[\Delta]^{d}$ of size at most $n$ presented as a stream of
$\operatorname{poly}(n)$ insertions and deletions of points, returns an
$O(\alpha)$-approximation (value and a set of centers) to capacitated
$k$-center on $P$. The algorithm uses $\operatorname{poly}(k2^{d/\alpha}\log
n)$ bits of space and fails with probability at most
$1/\operatorname{poly}(n)$.

#### Fair $k$-Center.

This variant is a special case of $k$-center with an assignment constraint,
and we use the specific formulation introduced in [SSS19].999Our approach can
also yield a similar result even if we use a more sophisticated formulation
introduced in [HJV19], where each point is allowed to be assigned to multiple
colors. We choose to present the result under the simpler [SSS19] model for
the sake of presentation. The input is a set $P\subset\mathbb{R}^{d}$ of $n$
points, two numbers $a,b$, and a coloring
$c\mathrel{\mathop{\ordinarycolon}}P\to\\{1,...,\ell\\}$. The assignment
constraint is that in every cluster $C$, for every color $i\in[\ell]$,

$\frac{|\\{p\in C\mathrel{\mathop{\ordinarycolon}}c(p)=i\\}|}{|\\{p\in
P\mathrel{\mathop{\ordinarycolon}}c(p)=i\\}|}\in[a,b].$

######  Corollary 4.6.

For every fixed $\ell\geq 1$, there is a randomized algorithm that, given as
input $\alpha>1,a,b,k,n,d,\Delta$ and set $P\subset[\Delta]^{d}$ of size at
most $n$ presented as a stream of $\operatorname{poly}(n)$ insertions and
deletions of points where every pointed is given with a color from $[\ell]$,
returns an $O(\alpha)$-approximation (value and a set of centers) to fair
$k$-center on $P$. The algorithm uses
$\ell\operatorname{poly}(k2^{d/\alpha}\log n)$ bits of space and fails with
probability at most $1/\operatorname{poly}(n)$.

##  5 Dimension Reduction for $k$-Center in Doubling Sets

In this section, we prove Theorem 1.5. More formally, we prove the following.

######  Theorem 5.1 (Dimension Reduction for Doubling Sets).

Let $P\subset\mathbb{R}^{d}$ be a set of doubling dimension
$\operatorname{ddim}(P)$, let $k\leq|P|$ and $0<\epsilon<1$, and suppose
$G\in\mathbb{R}^{t\times d}$ is a matrix of iid Gaussians $N(0,\tfrac{1}{t})$
for $t=O(\tfrac{\log
k}{\epsilon^{2}}+\tfrac{\log(1/\epsilon)}{\epsilon^{2}}\operatorname{ddim}(P))$.
Then with probability at least $2/3$,

  * •

the $k$-center value of $G(P)$ is a $(1+\epsilon)$-approximation for the
$k$-center value of $P$, and

  * •

$C\subset P$ is an $\alpha(1+\epsilon)$-approximate vanilla $k$-center
solution of $P$ whenever $G(C)$ is an $\alpha$-approximate vanilla $k$-center
solution of $G(P)$.

In fact, the bounds of Theorem 5.1 hold also for the assignment constraint
variant, following a similar analysis as in Section 4.

For the variant with outliers, the bounds are slightly different, as follows.

######  Theorem 5.2 (Doubling Sets, With Outliers, informal).

Under the conditions of Theorem 5.1, let $z<|P|$, then for
$t=O(\tfrac{\log(kz)}{\epsilon^{2}}+\tfrac{\log(1/\epsilon)}{\epsilon^{2}}\operatorname{ddim}(P))$,
the conclusion of Theorem 5.1 holds for $k$-center with $z$ outliers.

We prove the following lemmas, and get Theorems 5.1 and 5.2 as corollaries.

######  Lemma 5.3.

Under the same conditions of Theorem 5.1,

$\Pr[\forall x,y\in P,\|Gx-
Gy\|\geq\epsilon(\|x-y\|+\operatorname{opt}_{vanilla}(P))]\leq 2/3.$

######  Lemma 5.4.

Under the same conditions of Theorem 5.2,

$\Pr[\forall x,y\in P,\|Gx-
Gy\|\geq\epsilon(\|x-y\|+\operatorname{opt}_{outliers}(P))]\leq 2/3.$

A key lemma in our proof of Lemmas 5.3 and 5.4 is the following, which was
proved by Indyk and Naor [IN07].

######  Lemma 5.5 (Lemma 4.2 [IN07]).

Let $X\subset B(0,1)$ be a subset of an Euclidean unit ball. Then there are
universal constants $c,C>0$ such that for $t>C\operatorname{ddim}(X)+1$,

$\Pr(\exists x\in X,\|Gx\|>6)\leq e^{-ct}.$

###### Proof of Lemma 5.3.

Denote by $D$ the vanilla $k$-center value of $P$. Consider an $\epsilon
D$-net for the set $P$, i.e., a minimal set $Y\subseteq P$ such that for every
$x\in P$ there exists $y\in Y$ satisfying $\|x-y\|\leq\epsilon D$. By the
doubling assumption, the size of this net is $|Y|\leq
k(1/\epsilon)^{\operatorname{ddim}(P)}$, by the following. Let $I_{0}$ be an
optimal set of centers for vanilla $k$-center of $P$. Clearly
$P\subseteq\bigcup_{x\in I_{0}}B(x,D)$, thus by the doubling assumption there
exists $I_{1}=S\subseteq P$ of size $|S|\leq
2^{\operatorname{ddim}(P)}|I_{0}|$ such that $P\subseteq\bigcup_{s\in
S}B(s,D/2)$. Continue by induction for $\log\tfrac{1}{\epsilon}$ levels to get
balls of radius $\epsilon D$. The size of the set is then
$|Y|\leq|I_{\log\tfrac{1}{\epsilon}}|\leq
2^{\operatorname{ddim}(P)}|I_{\log\tfrac{1}{\epsilon}-1}|\leq...\leq(2^{\operatorname{ddim}(P)})^{\log\tfrac{1}{\epsilon}}|I_{0}|=k(1/\epsilon)^{\operatorname{ddim}(P)}$.

For
$t=O(\epsilon^{-2}\log|Y|)=O(\epsilon^{-2}(\log(1/\epsilon)\operatorname{ddim}(P)+\log
k))$, by 2.2 and a union bound, with probability $9/10$, we have

$\forall y_{1},y_{2}\in
Y,\qquad\|Gy_{1}-Gy_{2}\|\in(1\pm\epsilon)\|y_{1}-y_{2}\|.$

Now consider each $y\in Y$ separately. By Lemma 5.5, with probability
$1-e^{-ct}$, every $x\in B(y,\epsilon D)$ satisfy $\|G(x-y)\|\leq 6\epsilon
D$. Thus by a union bound, this succeeds for all $y\in Y$ with probability
$1-e^{-ct}(1/\epsilon)^{\operatorname{ddim}(P)}\geq 9/10$.

By another union bound and by the triangle inequality, with probability $4/5$,
the pairwise distances of elements in $P$ is preserved (under the linear map
$G$) up to additive error $15\epsilon D$, which completes the proof (by
changing $\epsilon$ by a constant factor). ∎

###### Proof of Lemma 5.4.

Denote by $D$ the value of $k$-center with $z$ outliers of $P$. Let $Z^{*}$ be
the set of optimal outliers. Consider an $\epsilon D$-net $Y$ for the set
$P\setminus Z^{*}$. As in the proof of Lemma 5.3, by the doubling assumption,
$|Y|\leq k(1/\epsilon)^{\operatorname{ddim}(P)}$.

For
$t=O(\epsilon^{-2}\log(|Y|z))=O(\epsilon^{-2}(\log(1/\epsilon)\operatorname{ddim}(P)+\log
k+\log z))$, by 2.2 and a union bound, with probability $9/10$, we have

$\forall y_{1},y_{2}\in Y\cup
Z^{*},\qquad\|Gy_{1}-Gy_{2}\|\in(1\pm\epsilon)\|y_{1}-y_{2}\|.$

Now consider each $y\in Y$ separately. By Lemma 5.5, with probability
$1-e^{-ct}$, every $x\in B(y,\epsilon D)$ satisfy $\|G(x-y)\|\leq 6\epsilon
D$. Thus by a union bound, this succeeds for all $y\in Y$ with probability
$1-e^{-ct}(1/\epsilon)^{\operatorname{ddim}(P)}\geq 9/10$.

By another union bound and by the triangle inequality, with probability $4/5$,
the pairwise distances of elements in $P$ is preserved (under the linear map
$G$) up to additive error $15\epsilon D$, which completes the proof (by
changing $\epsilon$ by a constant factor). ∎

## References

  * [AC06] Nir Ailon and Bernard Chazelle.  Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform.  In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC, pages 557–563, 2006.  doi:10.1145/1132516.1132597.
  * [Ach03] Dimitris Achlioptas.  Database-friendly random projections: Johnson-Lindenstrauss with binary coins.  J. Comput. Syst. Sci., 66(4):671–687, 2003.  doi:10.1016/S0022-0000(03)00025-4.
  * [ACLM23] Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, and Pasin Manurangsi.  On the fine-grained complexity of approximating _k_ -center in sparse graphs.  In Symposium on Simplicity in Algorithms, SOSA, pages 145–155. SIAM, 2023.  doi:10.1137/1.9781611977585.ch14.
  * [ADIW09] Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David P. Woodruff.  Efficient sketches for earth-mover distance, with applications.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pages 324–330. IEEE Computer Society, 2009.  doi:10.1109/FOCS.2009.25.
  * [AEP18] Evangelos Anagnostopoulos, Ioannis Z. Emiris, and Ioannis Psarros.  Randomized embeddings with slack and high-dimensional approximate nearest neighbor.  ACM Trans. Algorithms, 14(2):18:1–18:21, 2018.  doi:10.1145/3178540.
  * [AIK08] Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer.  Earth mover distance over high-dimensional spaces.  In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 343–352, 2008.  URL: http://dl.acm.org/citation.cfm?id=1347082.1347120.
  * [AP02] Pankaj K. Agarwal and Cecilia Magdalena Procopiuc.  Exact and approximation algorithms for clustering.  Algorithmica, 33(2):201–226, 2002.  doi:10.1007/s00453-001-0110-y.
  * [AS15] Pankaj K. Agarwal and R. Sharathkumar.  Streaming algorithms for extent problems in high dimensions.  Algorithmica, 72(1):83–98, 2015.  doi:10.1007/s00453-013-9846-4.
  * [BBC+19] Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn.  Oblivious dimension reduction for $k$-means: beyond subspaces and the Johnson-Lindenstrauss Lemma.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1039–1050, 2019.  doi:10.1145/3313276.3316318.
  * [BCJ+22] Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu.  The power of uniform sampling for coresets.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 462–473, 2022.  doi:10.1109/FOCS54457.2022.00051.
  * [BFL+17] Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F. Yang.  Clustering high dimensional dynamic data streams.  In Proceedings of the 34th International Conference on Machine Learning, ICML, volume 70 of Proceedings of Machine Learning Research, pages 576–585. PMLR, 2017.  URL: http://proceedings.mlr.press/v70/braverman17a.html.
  * [BFS21] Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov.  On coresets for fair clustering in metric and euclidean spaces and their applications.  In 48th International Colloquium on Automata, Languages, and Programming, ICALP, volume 198 of LIPIcs, pages 23:1–23:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.23, doi:10.4230/LIPICS.ICALP.2021.23.
  * [BKP93] Judit Bar-Ilan, Guy Kortsarz, and David Peleg.  How to allocate network centers.  J. Algorithms, 15(3):385–415, 1993.  doi:10.1006/jagm.1993.1047.
  * [BZD10] Christos Boutsidis, Anastasios Zouzias, and Petros Drineas.  Random projections for $k$-means clustering.  In 24th Annual Conference on Neural Information Processing Systems, NeurIPS, pages 298–306. Curran Associates, Inc., 2010.  URL: https://proceedings.neurips.cc/paper/2010/hash/73278a4a86960eeb576a8fd4c9ec6997-Abstract.html.
  * [CCFM04] Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani.  Incremental clustering and dynamic information retrieval.  SIAM J. Comput., 33(6):1417–1440, 2004.  doi:10.1137/S0097539702418498.
  * [CCJ+23] Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten.  Streaming Euclidean MST to a Constant Factor.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC, pages 156–169, 2023.  doi:10.1145/3564246.3585168.
  * [CEM+15] Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu.  Dimensionality reduction for k-means clustering and low rank approximation.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pages 163–172, 2015.  doi:10.1145/2746539.2746569.
  * [CFJ+22] Artur Czumaj, Arnold Filtser, Shaofeng H-C Jiang, Robert Krauthgamer, Pavel Veselỳ, and Mingwei Yang.  Streaming facility location in high dimension via geometric hashing.  CoRR, 2022.  The latest version has additional results compared to the preliminary version in [CJK+22].  arXiv:2204.02095.
  * [CJK+22] Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang.  Streaming facility location in high dimension via geometric hashing.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 450–461, 2022.  doi:10.1109/FOCS54457.2022.00050.
  * [CJK23] Xiaoyu Chen, Shaofeng H.-C. Jiang, and Robert Krauthgamer.  Streaming Euclidean Max-Cut: Dimension vs data reduction.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC, pages 170–182, 2023.  doi:10.1145/3564246.3585170.
  * [CJLW22] Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten.  New streaming algorithms for high dimensional EMD and MST.  In 54th Annual Symposium on Theory of Computing, STOC, pages 222–233. ACM, 2022.  doi:10.1145/3519935.3519979.
  * [CKLV17] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii.  Fair clustering through fairlets.  In Annual Conference on Neural Information Processing Systems, NeurIPS, pages 5029–5037, 2017.  URL: https://proceedings.neurips.cc/paper/2017/hash/978fce5bcc4eccc88ad48ce3914124a2-Abstract.html.
  * [Cla99] Kenneth L. Clarkson.  Nearest neighbor queries in metric spaces.  Discret. Comput. Geom., 22(1):63–93, 1999.  doi:10.1007/PL00009449.
  * [CPP19] Matteo Ceccarello, Andrea Pietracaprina, and Geppino Pucci.  Solving $k$-center clustering (with outliers) in MapReduce and streaming, almost as accurately as sequentially.  Proc. VLDB Endow., 12(7):766–778, 2019.  doi:10.14778/3317315.3317319.
  * [CSS16] Vincent Cohen-Addad, Chris Schwiegelshohn, and Christian Sohler.  Diameter and $k$-Center in Sliding Windows.  In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016.  doi:10.4230/LIPIcs.ICALP.2016.19.
  * [CW22] Moses Charikar and Erik Waingarten.  The Johnson-Lindenstrauss Lemma for clustering and subspace approximation: From coresets to dimension reduction.  CoRR, 2022.  arXiv:2205.00371.
  * [dBBM23] Mark de Berg, Leyla Biabani, and Morteza Monemizadeh.  $k$-center clustering with outliers in the MPC and streaming model.  In IEEE International Parallel and Distributed Processing Symposium, IPDPS 2023, pages 853–863. IEEE, 2023.  doi:10.1109/IPDPS54959.2023.00090.
  * [dBMZ21] Mark de Berg, Morteza Monemizadeh, and Yu Zhong.  $k$-center clustering with outliers in the sliding-window model.  In 29th Annual European Symposium on Algorithms, ESA, volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.ESA.2021.13.
  * [DG03] Sanjoy Dasgupta and Anupam Gupta.  An elementary proof of a theorem of Johnson and Lindenstrauss.  Random Struct. Algorithms, 22(1):60–65, 2003.  doi:10.1002/rsa.10073.
  * [DKS10] Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós.  A sparse Johnson–Lindenstrauss transform.  In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC, pages 341–350, 2010.  doi:10.1145/1806689.1806737.
  * [FM90] Peter Frankl and Hiroshi Maehara.  Some geometric applications of the beta distribution.  Ann. Inst. Stat. Math., 42(3):463–474, 1990.  doi:10.1007/BF00049302.
  * [GKL03] Anupam Gupta, Robert Krauthgamer, and James R. Lee.  Bounded geometries, fractals, and low-distortion embeddings.  In 44th Symposium on Foundations of Computer Science, FOCS, pages 534–543. IEEE Computer Society, 2003.  doi:10.1109/SFCS.2003.1238226.
  * [Gon85] Teofilo F. Gonzalez.  Clustering to minimize the maximum intercluster distance.  Theor. Comput. Sci., 38:293–306, 1985.  doi:10.1016/0304-3975(85)90224-5.
  * [HJV19] Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheeth K. Vishnoi.  Coresets for clustering with fairness constraints.  In Advances in Neural Information Processing Systems 32, NeurIPS, pages 7587–7598, 2019.  URL: https://proceedings.neurips.cc/paper/2019/hash/810dfbbebb17302018ae903e9cb7a483-Abstract.html.
  * [HSYZ18] Wei Hu, Zhao Song, Lin F. Yang, and Peilin Zhong.  Nearly optimal dynamic $k$-means clustering for high-dimensional data.  2018\.  arXiv:1802.00459.
  * [IM98] Piotr Indyk and Rajeev Motwani.  Approximate nearest neighbors: Towards removing the curse of dimensionality.  In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, STOC, pages 604–613, 1998.  doi:10.1145/276698.276876.
  * [IN07] Piotr Indyk and Assaf Naor.  Nearest-neighbor-preserving embeddings.  ACM Trans. Algorithms, 3(3):31, 2007.  doi:10.1145/1273340.1273347.
  * [Ind03] Piotr Indyk.  Better algorithms for high-dimensional proximity problems via asymmetric embeddings.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 539–545, 2003.  URL: http://dl.acm.org/citation.cfm?id=644108.644200.
  * [Ind04] Piotr Indyk.  Algorithms for dynamic geometric problems over data streams.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC, page 373–380, 2004.  doi:10.1145/1007352.1007413.
  * [JL84] William Johnson and Joram Lindenstrauss.  Extensions of Lipschitz maps into a Hilbert space.  Contemporary Mathematics, 26:189–206, 01 1984.  doi:10.1090/conm/026/737400.
  * [KA15] Sang-Sub Kim and Hee-Kap Ahn.  An improved data stream algorithm for clustering.  Comput. Geom., 48(9):635–645, 2015.  doi:10.1016/j.comgeo.2015.06.003.
  * [KM05] Boaz Klartag and Shahar Mendelson.  Empirical processes and random projections.  Journal of Functional Analysis, 225(1):229–245, 2005.  doi:10.1016/j.jfa.2004.10.009.
  * [KS00] Samir Khuller and Yoram J. Sussmann.  The capacitated _K_ -center problem.  SIAM J. Discret. Math., 13(3):403–418, 2000.  doi:10.1137/S0895480197329776.
  * [Lam10] Christiane Lammersen.  Approximation Techniques for Facility Location and Their Applications in Metric Embeddings.  PhD thesis, Dortmund, Technische Universität, 2010.
  * [LM00] B. Laurent and P. Massart.  Adaptive estimation of a quadratic functional by model selection.  The Annals of Statistics, 28(5):1302 – 1338, 2000.  doi:10.1214/aos/1015957395.
  * [LN17] Kasper Green Larsen and Jelani Nelson.  Optimality of the Johnson-Lindenstrauss lemma.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 633–638, 2017.  doi:10.1109/FOCS.2017.64.
  * [LSS09] Christiane Lammersen, Anastasios Sidiropoulos, and Christian Sohler.  Streaming embeddings with slack.  In 11th International Symposium on Algorithms and Data Structures, WADS, volume 5664 of Lecture Notes in Computer Science, pages 483–494. Springer, 2009.  doi:10.1007/978-3-642-03367-4\\_42.
  * [Mat08] Jirí Matousek.  On variants of the Johnson-Lindenstrauss Lemma.  Random Struct. Algorithms, 33(2):142–156, 2008.  doi:10.1002/rsa.20218.
  * [MK08] Richard Matthew McCutchen and Samir Khuller.  Streaming algorithms for $k$-center clustering with outliers and with anonymity.  In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, volume 5171 of Lecture Notes in Computer Science, pages 165–178. Springer, 2008.  doi:10.1007/978-3-540-85363-3\\_14.
  * [MMR19] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn.  Performance of Johnson-Lindenstrauss transform for $k$-means and $k$-medians clustering.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1027–1038, 2019.  doi:10.1145/3313276.3316350.
  * [Nel20] Jelani Nelson.  Dimensionality reduction in Euclidean space.  Notices of the American Mathematical Society, 67(10):1498–1507, 2020.  doi:10.1090/noti2166.
  * [NSIZ21] Shyam Narayanan, Sandeep Silwal, Piotr Indyk, and Or Zamir.  Randomized dimensionality reduction for facility location and single-linkage clustering.  In Proceedings of the 38th International Conference on Machine Learning, ICML, volume 139 of Proceedings of Machine Learning Research, pages 7948–7957. PMLR, 2021.  URL: http://proceedings.mlr.press/v139/narayanan21b.html.
  * [Rog63] C. A. Rogers.  Covering a sphere with spheres.  Mathematika, 10(2):157–164, 1963.  doi:10.1112/S0025579300004083.
  * [SSS19] Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler.  Fair coresets and streaming algorithms for fair $k$-means.  In Approximation and Online Algorithms - 17th International Workshop, WAOA, volume 11926 of Lecture Notes in Computer Science, pages 232–251. Springer, 2019.  doi:10.1007/978-3-030-39479-0\\_16.
  * [Ver18] Roman Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.  doi:10.1017/9781108231596.
  * [WY22] David P. Woodruff and Taisuke Yasuda.  High-dimensional geometric streaming in polynomial space.  In 63rd Annual Symposium on Foundations of Computer Science, FOCS, pages 732–743. IEEE, 2022.  doi:10.1109/FOCS54457.2022.00075.

##  Appendix A On the Optimallity of Theorem 1.1

Our bound for $\alpha$-estimation of vanilla $k$-center is nearly optimal when
the dimension reduction is defined via a matrix $G$ of iid Gaussians (and
plausibly for all JL maps). We focus first on the leading term $O(\tfrac{\log
n}{\alpha^{2}})$, and show that it is tight. Consider the diameter problem,
whose value is within factor $2$ of the $1$-center value. By letting $P$ be
points on a one-dimensional line, one can see that the scaling factor of $G$
must be $\Omega(1/\sqrt{t})$. Now let $P$ be an $\epsilon$-net of the unit
sphere, say for $\epsilon=0.1$, which can be realized with $d=\Theta(\log n)$.
Then with high probability, $G$ stretches some unit vector to length
$\Omega(\sqrt{{d}/{t}})$ [Ver18, Theorem 4.6.1], hence there is some pair of
points in $G(P)$ whose distance is at least $\Omega(\sqrt{{d}/{t}})$. Since
$G$ preserves the diameter, that distance is also bounded by $2\alpha$, and
altogether $t=\Omega(\tfrac{d}{\alpha^{2}})=\Omega(\tfrac{\log
n}{\alpha^{2}})$.

Similarly, the second term in our bound is nearly optimal, namely, the target
dimension must be $t=\Omega(\tfrac{\log k}{\log\alpha})$. For ease of
presentation, assume $G$ is a matrix of iid $N(0,\tfrac{1}{t})$, but we will
have to scale it at the end. On one hand, if $P$ is a set of $k$ orthonormal
vectors and the origin, then $\operatorname{opt}_{vanilla}(P)=\tfrac{1}{2}$,
and with high probability, $\operatorname{opt}_{vanilla}(G(P))\leq
2^{-\Omega(\tfrac{\log k}{t})}$, as follows. The probability that none of the
$k$ orthonormal vectors shrinks to length at most $1/\beta$ is

$\prod_{i=1}^{k}\big{(}1-\Pr[\|Ge_{i}\|\leq\tfrac{1}{\beta}]\big{)}=\big{(}1-\Pr[\|G_{1}\|\leq\tfrac{1}{\beta}]\big{)}^{k}\leq(1-(e\beta)^{-t})^{k}\approx
1-k(e\beta)^{-t},$

where $G_{1}$ denotes the first column of $G$. Hence, if
$\beta=2^{\Omega(\tfrac{\log k}{t})}$, then, with high probability, there is a
vector among the $k$ orthonormal vectors whose length shrinks to at most
$1/\beta$, and thus $\operatorname{opt}_{vanilla}(G(P))\leq\tfrac{1}{2\beta}$.
On the other hand, if $P$ is a set of points on a line, then $G$ preserves all
pairwise distances with high probability, hence
$\operatorname{opt}_{vanilla}(G(P))=O(\operatorname{opt}_{vanilla}(P))$. Thus,
to get $\alpha$-approximation (after scaling $G$ appropriately), it must be
that $\alpha=\Omega(\beta)$, and hence $t=\Omega(\tfrac{\log k}{\log\alpha})$.

##  Appendix B Proof of Lemma 1.6

In order to prove Lemma 1.6, we will use the following fact about Gaussians.

######  Fact B.1.

For every $t\geq 1$ and a Gaussian $g\sim N(0,I_{t})$,

$\forall r\geq\sqrt{5t},\qquad\Pr\big{[}\|g\|\geq r\big{]}\leq e^{-r^{2}/5}.$

###### Proof.

By Laurent and Massart [LM00, Lemma 1],

$\forall x>0,\qquad\Pr\big{[}\|g\|^{2}-t\geq 2\sqrt{xt}+2x\big{]}\leq e^{-x}.$

Set $r^{2}=5x$, then $r^{2}\geq t+2\sqrt{xt}+2x$, and thus

$\Pr\big{[}\|g\|\geq r\big{]}\leq\Pr\big{[}\|g\|^{2}-t\geq
2\sqrt{xt}+2x\big{]}\leq e^{-x}=e^{-r^{2}/5}.$

∎

We will now prove Lemma 1.6, which states that for a $t\times d$ matrix $G$ of
Gaussians that are iid $N(0,1)$ and a suitable universal constant $c_{0}>0$,

$\Pr\big{[}\sup_{\|x\|\leq 1}\|Gx\|>c_{0}\sqrt{d}\big{]}\leq 2^{-\Omega(d)}.$

###### Proof of Lemma 1.6..

Denote $T=c_{0}\sqrt{d}$. For every $x\in\mathbb{R}^{d}$ and $r>0$, denote
$B(x,r)=\mathinner{\left\\{y\in\mathbb{R}^{d}\mathrel{\mathop{\ordinarycolon}}\|x-y\|\leq
r\right\\}}$. Consider subsets $I_{0},I_{1},I_{2},...\subset B(0,1)$ as
follows. Let $I_{0}=\mathinner{\left\\{0\right\\}}$. For every $y\in I_{j}$,
let $S_{j}(y)$ be a minimal set such that $\bigcup_{s\in
S_{j}(y)}B(s,2^{-j-1})$ covers $B(y,2^{-j})$. Clearly, $\|y-s\|\leq 2^{-j}$.
Let $I_{j+1}=\bigcup_{y\in I_{j}}S_{j}(y)$. It then holds that $|S_{j}(y)|\leq
e^{O(d)}$ (see e.g. [Rog63]). By induction, $|I_{j}|\leq e^{O(jd)}$.

For every $y\in I_{j}$ and $s\in S_{j}(y)$,

$\displaystyle\Pr\big{[}\|G(y-s)\|>\tfrac{T}{4}(\tfrac{4}{3})^{-j}\big{]}$
$\displaystyle\leq\Pr\big{[}\|G(y-s)\|>\tfrac{T}{4}(\tfrac{4}{3})^{-j}\|y-s\|2^{j}\big{]}$
since $G\tfrac{y-s}{\|y-s\|}\sim N(0,I_{t})$, then by B.1, $\displaystyle\leq
e^{-\Omega((T(2/3)^{-j})^{2})}=e^{-\Omega(d(2/3)^{-2j})}.$

By a union bound,

$\Pr\big{[}\exists y\in I_{j},s\in
S_{j}(y),\;\|G(y-s)\|>\tfrac{T}{4}(\tfrac{4}{3})^{-j}\big{]}\leq|I_{j+1}|\cdot
e^{-\Omega(d(2/3)^{-2j})}\leq e^{-\Omega(d(2/3)^{-2j})}.$

By another union bound, the probability that there exists $j\geq 0$ for which
the above event occurs, is at most
$\sum_{j=0}^{\infty}e^{-\Omega(d(2/3)^{-2j})}\leq e^{-\Omega(d)}$. Assuming
this event does not occur, then every $x\in B(0,1)$ satisfies $\|Gx\|\leq T$,
as follows. Every $x\in B(0,1)$ can be expressed as
$x=\sum_{j=0}^{\infty}a_{j}-a_{j+1}$ where $a_{j}\in I_{j}$ and $a_{j+1}\in
S_{j}(a_{j})$. Thus by the triangle inequality,
$\|Gx\|\leq\sum_{j=0}^{\infty}\|G(a_{j}-a_{j+1})\|\leq\sum_{j=0}^{\infty}\tfrac{T}{4}(\tfrac{4}{3})^{-j}=T$.
∎

##  Appendix C Dimension Reduction for FPQ

In this section, we design moderate dimension reduction for FPQ, and
demonstrate its application to streaming algorithms for $k$-center.

######  Theorem C.1.

Let $d,\alpha>1$ and $k\leq n$. There is a random linear map
$G\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{d}\to\mathbb{R}^{t}$ with
$t=O(\log k+\tfrac{d}{\alpha^{2}})$, such that for every two sets,
$P\subset\mathbb{R}^{d}$ of size $n$ and $Q\subset\mathbb{R}^{d}$ of size $k$,
with probability at least $2/3$,

  * •

the value $FPQ_{k}(G(P),G(Q))$ is an $O(\alpha)$-estimation for the value
$FPQ_{k}(P,Q)$, and

  * •

$p\in P$ is an $O(\alpha)$-approximate solution for $FPQ_{k}(P,Q)$ whenever
$Gp$ is an $O(1)$-approximate solution for $FPQ_{k}(G(P),G(Q))$.

###### Proof.

Let a point $p^{*}\in P$ such that $\operatorname{dist}(p^{*},Q)=\max_{p\in
P}\operatorname{dist}(p,Q)$, i.e., it realizes $FPQ_{k}(P,Q)$. Assume without
loss of generality that $\operatorname{dist}(p^{*},Q)=\alpha$, which can be
obtained by scaling all the points in $P\cup Q$ by an
$\tfrac{\alpha}{\operatorname{dist}(p^{*},Q)}$ factor. Pick
$T=\Theta(\sqrt{d})$ such that the hidden constant satisfies the condition in
Lemma 1.6, and pick $t=O(\log k)+400\tfrac{T^{2}}{\alpha^{2}}$ and
$\epsilon=\tfrac{1}{2}$, such that the bound in 2.2 is
$2^{-\Omega(t)}\leq\tfrac{1}{10k}$. Let $G$ be a $t\times d$ matrix of iid
Gaussians $N(0,1)$. Then, by 2.2 and a union bound,

$\Pr\big{[}\forall q\in Q,\;\|G(p^{*}-q)\|\in[1\pm
0.5]\sqrt{t}\|p^{*}-q\|\big{]}\geq 1-k2^{-\Omega(t)}\geq\tfrac{9}{10}.$ (6)

Equation 3 holds as in the proof of Theorem 2.1. Assuming the two events in
Equations 3 and 6 happen, then

$\operatorname{dist}(Gp^{*},G(Q))\geq\tfrac{1}{2}\sqrt{t}\operatorname{dist}(p^{*},Q)=\tfrac{1}{2}\sqrt{t}\alpha\geq
10T,$

and for every $x\in\mathbb{R}^{d}$ for which $\operatorname{dist}(x,Q)\leq 1$,

$\operatorname{dist}(Gx,G(Q))\leq T.$

Hence, for every $p\in P$, $\operatorname{dist}(Gp,G(Q))\leq
T\operatorname{dist}(p,Q)\leq\alpha T$. By scaling $G$, we get an
$O(\alpha)$-estimation.

Similarly, a $5$-approximate $FPQ_{k}(G(P),G(Q))$ is a point $Gp\in G(P)$ that
must satisfy $\operatorname{dist}(Gp,G(Q))\geq 2T$, hence it corresponds to a
point $p\in P$ such that
$\operatorname{dist}(p,Q)>1=\tfrac{1}{\alpha}\operatorname{dist}(p^{*},Q)$.
The constant $5$ in the approximation is arbitrary and could be changed to any
other constant by increasing $t$. This concludes the proof. ∎

We can employ Theorem C.1 to obtain a streaming $O(\alpha)$-approximation
algorithm for $FPQ_{k}(P,Q)$ using $\operatorname{poly}(k2^{d/\alpha^{2}}\log
n)$ bits of space, as follows. Notice that there is a streaming algorithm for
$(1+\epsilon)$-approximation of FPQ using $k\cdot
O(1/\epsilon)^{d}\operatorname{poly}(\log n)$ bits of space, similarly to the
algorithm for $k$-center in [dBBM23] (with the slight adaptation of using two-
level $\ell_{0}$-sampling, as mentioned in Section 1.4). Thus, we can apply
the dimension reduction of Theorem C.1 and then execute this algorithm, which
concludes the proof.

The algorithm obtained above for $FPQ$ can be used to devise an algorithm for
vanilla $k$-center, as discussed below. In particular, it yields an
$O(\alpha)$-approximation streaming algorithm for vanilla $k$-center using
$\operatorname{poly}(k2^{d/\alpha^{2}}\log n)$ bits of space (which is the
same bound as Corollary 2.3).

#### Approximating $k$-Center via Approximations for FPQ.

The following version of Gonzalez’s algorithm computes a
$(2\alpha)$-approximate $k$-center (value and solution). For sets
$P\subset\mathbb{R}^{d}$ and $Q\subset P$, $|Q|\leq k$, an _$\alpha$
-approximation to $FPQ_{k}(P,Q)$_ is a point $p\in P$ such that
$\operatorname{dist}(p,Q)\geq\tfrac{1}{\alpha}\max_{p^{\prime}\in
P}\operatorname{dist}(p^{\prime},Q)$.

######  Lemma C.2 (Relaxed Gonzalez).

Given as input numbers $n,k,\alpha$ and a pointset $P\subset\mathbb{R}^{d}$ of
size $n$, the following algorithm returns a $(2\alpha)$-approximation to
$k$-center on $P$.

  1. 1.

pick an arbitrary point $s_{1}\in P$ and let $S_{1}\leftarrow\\{s_{1}\\}$

  2. 2.

for $i=2,\ldots,k+1$

  3. 3.

pick a point $s_{i}\in P$ that is an $\alpha$-approximation to
$FPQ_{i-1}(P,S_{i-1})$

  4. 4.

$S_{i}\leftarrow S_{i-1}\cup\\{s_{i}\\}$

  5. 5.

$D\leftarrow\min_{p\neq q\in S_{k+1}}\|p-q\|$ // the distance between a
nearest pair of points in $S_{k+1}$

  6. 6.

output $S_{k}$ and $\alpha D$

######  Corollary C.3 (Informal).

Running in parallel $k$ executions of an $\alpha$-approximation algorithm for
$FPQ$ over the same input $P$ can be used to $(2\alpha)$-approximate vanilla
$k$-center on $P$.

###### Proof of Lemma C.2..

Lemma 4.1 of [ACLM23] proves that $S_{k}$ is a $2\alpha$-approximate solution
to $k$-center on $P$.

Denote by $\operatorname{opt}$ the $k$-center value of $P$. By the fact that
$|S_{k+1}|=k+1$ and by a triangle inequality, $D$ is at most $2$ times the
value of $k$-center on $S_{k+1}$, thus $D\leq 2\operatorname{opt}$. Suppose
$s_{i},s_{j}\in S_{k+1}$ for $1\leq j<i\leq k+1$ are a pair of points that
realize $D$, i.e., they are a nearest pair in $S_{k+1}$. Then, by construction
of the set $S_{i}$,

$\displaystyle D=\|s_{i}-s_{j}\|=\operatorname{dist}(s_{i},S_{i-1})$
$\displaystyle\geq\tfrac{1}{\alpha}\max_{q\in
P}\operatorname{dist}(q,S_{i-1})$ and since $\operatorname{opt}$ is the
minimum over all sets $C$ of size $k$,
$\displaystyle\geq\tfrac{1}{\alpha}\min_{C\subset\mathbb{R},|C|=k}\max_{q\in
P}\operatorname{dist}(q,C)=\tfrac{1}{\alpha}\operatorname{opt},$

which concludes the proof. ∎