#  $\mathcal{O}(\log^{*}n)$-approximation for $k$-Center in Sublinear MPC

Sam Coy111University of Warwick, UK Artur Czumaj11footnotemark: 1 Gopinath
Mishra11footnotemark: 1 Sam Coy Artur Czumaj Gopinath Mishra
Department of Computer Science
Centre for Discrete Mathematics and its Applications
University of Warwick Research supported in part by the Centre for Discrete
Mathematics and its Applications (DIMAP), by an EPSRC studentship, and by the
Simons Foundation Award No 663281 granted to the Institute of Mathematics of
the Polish Academy of Sciences for the years 2021-2023. Research supported in
part by the Centre for Discrete Mathematics and its Applications (DIMAP), by
EPSRC award EP/V01305X/1, by a Weizmann-UK Making Connections Grant, by an IBM
Award, and by the Simons Foundation Award No. 663281 granted to the Institute
of Mathematics of the Polish Academy of Sciences for the years
2021–2023.Research supported in part by the Centre for Discrete Mathematics
and its Applications (DIMAP), by EPSRC award EP/V01305X/1, and by the Simons
Foundation Award No 663281 granted to the Institute of Mathematics of the
Polish Academy of Sciences for the years 2021-2023. Sam Coy Artur Czumaj
Gopinath Mishra
University of Warwick E-mail<EMAIL_ADDRESS>Department of Computer
Science, University of Warwick, UK. Research supported in part by the Centre
for Discrete Mathematics and its Applications (DIMAP), by an EPSRC
studentship, and by the Simons Foundation Award No 663281 granted to the
Institute of Mathematics of the Polish Academy of Sciences for the years
2021-2023.E-mail<EMAIL_ADDRESS>Department of Computer Science and
Centre for Discrete Mathematics and its Applications, University of Warwick,
UK. Research supported in part by the Centre for Discrete Mathematics and its
Applications (DIMAP), by EPSRC award EP/V01305X/1, by a Weizmann-UK Making
Connections Grant, by an IBM Award, and by the Simons Foundation Award No.
663281 granted to the Institute of Mathematics of the Polish Academy of
Sciences for the years 2021–2023.E-mail<EMAIL_ADDRESS>Department of Computer Science, University of Warwick, UK. Research supported
in part by the Centre for Discrete Mathematics and its Applications (DIMAP),
by EPSRC award EP/V01305X/1, and by the Simons Foundation Award No 663281
granted to the Institute of Mathematics of the Polish Academy of Sciences for
the years 2021-2023. Sam Coy
University of Warwick E-mail<EMAIL_ADDRESS>Department of Computer
Science, University of Warwick, UK. Research supported in part by the Centre
for Discrete Mathematics and its Applications (DIMAP), by an EPSRC
studentship, and by the Simons Foundation Award No. 663281 granted to the
Institute of Mathematics of the Polish Academy of Sciences for the years
2021–2023. Artur Czumaj
University of Warwick E-mail<EMAIL_ADDRESS>Department of Computer
Science and Centre for Discrete Mathematics and its Applications, University
of Warwick, UK. Research supported in part by the Centre for Discrete
Mathematics and its Applications (DIMAP), by EPSRC award EP/V01305X/1, by a
Weizmann-UK Making Connections Grant, by an IBM Award, and by the Simons
Foundation Award No. 663281 granted to the Institute of Mathematics of the
Polish Academy of Sciences for the years 2021–2023. Gopinath Mishra
University of Warwick E-mail<EMAIL_ADDRESS>Department of
Computer Science, University of Warwick, UK. Research supported in part by the
Centre for Discrete Mathematics and its Applications (DIMAP), by EPSRC award
EP/V01305X/1, and by the Simons Foundation Award No. 663281 granted to the
Institute of Mathematics of the Polish Academy of Sciences for the years
2021–2023.

# On Parallel $k$-Center Clustering

Sam Coy111University of Warwick, UK Artur Czumaj11footnotemark: 1 Gopinath
Mishra11footnotemark: 1 Sam Coy Artur Czumaj Gopinath Mishra
Department of Computer Science
Centre for Discrete Mathematics and its Applications
University of Warwick Research supported in part by the Centre for Discrete
Mathematics and its Applications (DIMAP), by an EPSRC studentship, and by the
Simons Foundation Award No 663281 granted to the Institute of Mathematics of
the Polish Academy of Sciences for the years 2021-2023. Research supported in
part by the Centre for Discrete Mathematics and its Applications (DIMAP), by
EPSRC award EP/V01305X/1, by a Weizmann-UK Making Connections Grant, by an IBM
Award, and by the Simons Foundation Award No. 663281 granted to the Institute
of Mathematics of the Polish Academy of Sciences for the years
2021–2023.Research supported in part by the Centre for Discrete Mathematics
and its Applications (DIMAP), by EPSRC award EP/V01305X/1, and by the Simons
Foundation Award No 663281 granted to the Institute of Mathematics of the
Polish Academy of Sciences for the years 2021-2023. Sam Coy Artur Czumaj
Gopinath Mishra
University of Warwick E-mail<EMAIL_ADDRESS>Department of Computer
Science, University of Warwick, UK. Research supported in part by the Centre
for Discrete Mathematics and its Applications (DIMAP), by an EPSRC
studentship, and by the Simons Foundation Award No 663281 granted to the
Institute of Mathematics of the Polish Academy of Sciences for the years
2021-2023.E-mail<EMAIL_ADDRESS>Department of Computer Science and
Centre for Discrete Mathematics and its Applications, University of Warwick,
UK. Research supported in part by the Centre for Discrete Mathematics and its
Applications (DIMAP), by EPSRC award EP/V01305X/1, by a Weizmann-UK Making
Connections Grant, by an IBM Award, and by the Simons Foundation Award No.
663281 granted to the Institute of Mathematics of the Polish Academy of
Sciences for the years 2021–2023.E-mail<EMAIL_ADDRESS>Department of Computer Science, University of Warwick, UK. Research supported
in part by the Centre for Discrete Mathematics and its Applications (DIMAP),
by EPSRC award EP/V01305X/1, and by the Simons Foundation Award No 663281
granted to the Institute of Mathematics of the Polish Academy of Sciences for
the years 2021-2023. Sam Coy
University of Warwick E-mail<EMAIL_ADDRESS>Department of Computer
Science, University of Warwick, UK. Research supported in part by the Centre
for Discrete Mathematics and its Applications (DIMAP), by an EPSRC
studentship, and by the Simons Foundation Award No. 663281 granted to the
Institute of Mathematics of the Polish Academy of Sciences for the years
2021–2023. Artur Czumaj
University of Warwick E-mail<EMAIL_ADDRESS>Department of Computer
Science and Centre for Discrete Mathematics and its Applications, University
of Warwick, UK. Research supported in part by the Centre for Discrete
Mathematics and its Applications (DIMAP), by EPSRC award EP/V01305X/1, by a
Weizmann-UK Making Connections Grant, by an IBM Award, and by the Simons
Foundation Award No. 663281 granted to the Institute of Mathematics of the
Polish Academy of Sciences for the years 2021–2023. Gopinath Mishra
University of Warwick E-mail<EMAIL_ADDRESS>Department of
Computer Science, University of Warwick, UK. Research supported in part by the
Centre for Discrete Mathematics and its Applications (DIMAP), by EPSRC award
EP/V01305X/1, and by the Simons Foundation Award No. 663281 granted to the
Institute of Mathematics of the Polish Academy of Sciences for the years
2021–2023.

###### Abstract

We consider the classic $k$-center problem in a parallel setting, on the low-
local-space Massively Parallel Computation (MPC) model, with local space per
machine of $\mathcal{O}(n^{\delta})$, where $\delta\in(0,1)$ is an arbitrary
constant. As a central clustering problem, the $k$-center problem has been
studied extensively. Still, until very recently, all parallel MPC algorithms
have been requiring $\Omega(k)$ or even $\Omega(kn^{\delta})$ local space per
machine. While this setting covers the case of small values of $k$, for a
large number of clusters these algorithms require large local memory, making
them poorly scalable. The case of large $k$, $k\geq\Omega(n^{\delta})$, has
been considered recently for the low-local-space MPC model by Bateni et al.
(2021), who gave an $\mathcal{O}(\log\log n)$-round MPC algorithm that
produces $k(1+o(1))$ centers whose cost has multiplicative approximation of
$\mathcal{O}(\log\log\log n)$. In this paper we extend the algorithm of Bateni
et al. and design a low-local-space MPC algorithm that in
$\mathcal{O}(\log\log n)$ rounds returns a clustering with $k(1+o(1))$
clusters that is an $\mathcal{O}(\log^{*}n)$-approximation for $k$-center.

##  1 Introduction

Clustering large data is a fundamental primitive extensively studied because
of its numerous applications in a variety of areas of computer science and
data science. It is a central type of problem in modern data analysis,
including the fields of data mining, pattern recognition, machine learning,
networking and social networks, and bioinformatics. In a typical clustering
problem, the goal is to partition the input data into subsets (called
clusters) such that the points assigned to the same cluster are “similar” to
one another, and data points assigned to different clusters are “dissimilar”.

The most extensively studied clustering problems are $k$-means, $k$-median,
$k$-center, various notions of hierarchical clustering, and also variants of
these problems with some additional constraints (e.g., fairness or balance).

While originally the clustering problems have been studied in the context of
classical sequential computation, most recently a large amount of research has
been devoted to the non-sequential computational settings such as distributed
and parallel computing, mainly because these are the only settings capable of
performing computations in a reasonable time on large inputs, and because data
is frequently collected on different sites and clustering needs to be
performed in a distributed manner with low communication.

In this paper we consider one of the most fundamental clustering problems, the
_$k$ -center_ problem, on the _Massively Parallel Computation (MPC)_ model.
MPC is a modern theoretical model of parallel computation, inspired by
frameworks such as MapReduce [DG08], Hadoop [Whi15], Dryad [IBY+07], and Spark
[ZCF+10]. Introduced just over a decade ago by Karloff et al. [KSV10] (and
later refined, e.g., in [ANOY14, BKS17, CŁM+18, GSZ11]), the model has been
the subject of an increasing quantity of fundamental research in recent years,
becoming nowadays the standard theoretical parallel model of algorithmic
study.

MPC is a parallel system with ${\mathrm{m}}$ _machines_ , each with
${\mathrm{s}}$ words of _local memory_. (We also consider the _global space_
${\mathrm{g}}$, which is the total space used across all machines,
${\mathrm{g}}={\mathrm{s}}\cdot{\mathrm{m}}$.) Computation takes place in
synchronous rounds: in each round, each machine may perform arbitrary
computation on its local memory, and then exchange messages with other
machines. Each message is sent to a single machine specified by the machine
sending the message. Machines must send and receive at most ${\mathrm{s}}$
words each round. The messages are processed by recipients in the next round.
At the end of the computation, machines collectively output the solution. The
goal is to design an MPC algorithm that solves a given task in as few rounds
as possible.

If the input is of size $n$, then one wants ${\mathrm{s}}$ to be sublinear in
$n$ (for if ${\mathrm{s}}\geq n$ then a single machine can solve any problem
without any communication, in a single round), and the total space across all
the machines to be at least $n$ (in order for the input to fit onto the
machines) and ideally not much larger. In this paper, we focus on the _low-
local-space_ MPC setting, where the local space of each machine is strongly
sublinear in the input size, i.e., ${\mathrm{s}}=\mathcal{O}(n^{\delta})$ for
some arbitrarily constant $\delta\in(0,1)$. This low-local-space regime is
especially attractive because of its scalability. At the same time, this
setting is particularly challenging in that it requires extensive inter-
machine communication to solve clustering problems for the input data
scattered over many machines.

In recent years we have seen a number of very efficient, often constant-time,
parallel clustering algorithms that have been relying on a combination of a
_core-set_ and a “reduce-and-merge” approach. In this setting, one gradually
filters the data set by typically reducing its size on every machine to
$\widetilde{\mathcal{O}}(k)$, continuing until all the data can be stored on a
single machine, at which point the problem is solved locally. Observe that
this approach has an inherent bottleneck that requires that any machine must
be able to store $\Omega(k)$ data points. Intuitively, this follows from the
fact that if a machine sees $k$ data points that are all very far away from
each other, it needs to keep track of all $k$ of them, for otherwise it might
miss all the information about one of the clusters, which in turn could lead
to a large miscalculation of the objective value. Similar arguments could be
also used to argue that each machine needs to communicate $\Omega(k)$ points
to the others (see [CSWZ16] for a formalization of such intuition for a
_worst-case partition_ of points for $k$-median, $k$-means, and $k$-center
problems, though the worst-case partition assumption means that this bound
does not extend directly to MPC). Because of that, most of the earlier
clustering MPC algorithms, especially those working in a constant number of
rounds (see, e.g., [EIM11, MKC+15]), require $\Omega(k)$ or even
$\Omega(k)\cdot n^{\Omega(1)}$ local space. Therefore in the setting
considered in this paper, of MPC with local space per machine of
${\mathrm{s}}=\mathcal{O}(n^{\delta})$, the approach described above cannot be
applied when the number of clusters is large, when $k=\omega({\mathrm{s}})$.
This naturally leads to the main challenge in the design of clustering
algorithms for MPC with low-local-space: _how to efficiently partition the
data into $k$ good quality clusters on an MPC with local space
${\mathrm{s}}\ll k$_. We believe that this setting is quantitatively different
(and more challenging) from the setting when $k$ is smaller (or even
comparable to) the amount of local space ${\mathrm{s}}$.

In this paper, we focus on the _$k$ -center clustering problem_, a standard,
widely studied, and widely used formulation of metric clustering. The problem
is, given a set of $n$ input points, to find a subset of size $k$ of these
points (called _centers_) such that that maximum distance of a point to its
nearest center is minimized. Specifically, in this work, we focus on the case
where $k\gg{\mathrm{s}}$ and hence, when $k$ is quite large relative to $n$:
one can think of these problem instances as “compressing” the input set of $n$
points into $k$ points. Very recently this problem has been addressed by
Bateni et al. [BEFM21], who showed one can design an $\mathcal{O}(\log\log
n)$-round MPC algorithm, with local space
${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global space
${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\delta})$,222$\widetilde{\mathcal{O}}(f)$
hides a polynomial factor in $\log f$. that returns an
$\mathcal{O}(\log\log\log n)$-approximate solution with $k+o(k)$ centers. Our
main result is an improved bound in the MPC model:

######  Theorem 1.1 (Main result stated informally).

In $\mathcal{O}(\log\log n)$ rounds on an MPC, we can compute an
$\mathcal{O}(\log^{*}n)$ approximate solution to the $k$-centers problem using
$k(1+o(1))$ centers.

The MPC has local space ${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global
space ${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\rho})$ for any constant
$\rho>0$. The $n$ input points are in $\mathbb{R}^{d}$ for some constant $d$
and we assume that $k=\Omega(\log^{c}n)$ for a suitable constant $c$. Our
algorithm succeeds with high probability.

The algorithmic framework is based on a repeated application of _locally
sensitive sampling_ : sampling a set of “hub” points, assigning all other
points to a nearby hub, and then adding new hubs to well-approximate the point
set. We improve the approximation factor by a careful examination of the
progress of clusters in some fixed optimal clustering over the course of the
algorithm. Due to the depth of our iteration, clusters no longer satisfy
certain properties with high probability, and carefully bounding the size of
the clusters that fail to meet certain checks is an important challenge to
overcome in our analysis. Additionally, we provide a more flexible guarantee
on the global space, providing an accuracy parameter which can be set to
reduce global space used at the expense of a larger approximation ratio (or
vice versa).333In particular, the constant in $\mathcal{O}(\log^{*}n)$ of 1.1
depends on $\rho$. This is possible because of the way we implement _locally-
sensitive hashing (LSH)_ in MPC. We believe our implementation of LSH in MPC
could potentially see further applications, e.g., for other geometric
problems.

###  1.1 Related work

There has been a large amount of work on various variants of the clustering
problems (see, e.g., [XW05] for a survey of research until 2005), including
some extensive study of the $k$-center clustering problem. The $k$-center
problem is well known to be NP-hard and simple algorithms are known to achieve
a 2-approximation [DF85, Gon85, HS85]; this approximation ratio is tight
unless $\mathrm{P}=\mathrm{NP}$ [HN79].

The study of clustering in the context of parallel computing is extremely
well-motivated: as the size of typical data sets continue to increase, it
becomes infeasible to store input data on a single machine, let alone iterate
over it many times (as greedy sequential algorithms require (see, e.g.,
[Gon85])). It comes therefore as no surprise that there has been a
considerable amount of work on $k$-center clustering algorithms in MPC. In
particular, several constant-round, constant-approximation algorithms in the
MPC setting were given recently for general metric $k$-center clustering, see,
e.g., [EIM11, MKC+15, CPP19]. Much of this work used _coresets_ or similar
techniques as a means of approximating the structure of the underlying data,
naturally implying a requirement that the local space satisfies
${\mathrm{s}}=\Omega(k)$ per machine and global space is
${\mathrm{g}}=\Omega(nk)$ or $\Omega(n^{\epsilon}k^{2})$ [EIM11, MKC+15,
CPP19]. Specifically, Ene et al. [EIM11] gave a $\mathcal{O}(1)$ round
$10$-approximation MPC algorithm that uses local space
${\mathrm{s}}=\mathcal{O}(k^{2}n^{\Theta(1)})$, Malkomes et al. [MKC+15]
obtained a $2$-round $4$-approximation MPC algorithm with local space
${\mathrm{s}}=\Omega(\sqrt{nk})$, and Ceccarello et al. [CPP19] obtained a
$2$-round $(2+\varepsilon)$-approximation MPC algorithm that uses local space
${\mathrm{s}}=\mathcal{O}_{d,\varepsilon}(\sqrt{nk})$ for the problem in
metric spaces with doubling dimension $d$. As mentioned earlier, these
algorithms are not scalable if $k$ is large relative to $n$ (for example, when
$k=n^{1/3}$), making the case of large $k$ particularly challenging.
Furthermore, as argued by Bateni et al. [BEFM21], the case of large $k$
appears naturally in some applications of $k$ clustering, including label
propagation used in semi-supervised learning, or same-meaning query clustering
for online advertisement or document search [WLF+09]. Unfortunately, we do not
know of any $O(1)$-round, $O(1)$-approximation MPC algorithm that would use
local space ${\mathrm{s}}=o(k)$.

In order to address the case of large $k$, Bateni et al. [BEFM21] considered a
relaxed version of $k$-center clustering for low dimensional Euclidean spaces
with constant dimension. The goal of that work was to design a scalable MPC
algorithm for the $k$-center clustering problem with a _sublogarithmic number
of rounds_ of computation, _sublinear space per machine_ , and small global
space. Bateni et al. [BEFM21] showed that in $\mathcal{O}(\log\log n)$ rounds
on an MPC with ${\mathrm{s}}=\mathcal{O}(n^{\delta})$, one can compute an
$\mathcal{O}(\log\log\log n)$-approximate solution to constant-dimension
Euclidean $k$-center with $k(1+o(1))$ centers. Their algorithm uses
$\widetilde{\mathcal{O}}(n^{1+\delta}\cdot\log\Delta)$ global space. Bateni et
al. [BEFM21] complemented their analysis by some empirical study to
demonstrate that the designed algorithm performs well in practice.

Finally, in the related PRAM model of parallel computation Blelloch and
Tangwonsan gave a $2$-approximation algorithm for $k$-center [BT10]. However,
their algorithm requires $\Omega(n^{2})$ processors and it is therefore
difficult to translate the approach to our setting.

###  1.2 Technical contributions

Our main result in 1.1 is an extension of the approach developed in Bateni et
al. [BEFM21] that significantly improves the quality of the approximation
guarantee. To present these two results in the right context, we will briefly
describe the main differences between these two works at a high level.

The approach of Bateni et al. [BEFM21] starts with the entire point set $P$ as
a set of potential centers (solution), and refines it to
$P=P_{0}\supseteq\dots\supseteq P_{\tau}$, until
$\left|P_{\tau}\right|=k+o(k)$. The final set $P_{\tau}$ is reported as the
output. It is not difficult to see that if we take an optimal clustering
$\mathcal{C}^{*}$ for $P$ (i.e., $\mathcal{C}^{*}$ is the optimal solution to
the $k$-center problem for $P$), then the number of potential centers in any
cluster $C\in\mathcal{C}^{*}$ reduces over rounds (that is, $|P_{i+1}\cap
C|\leq|P_{i}\cap C|$). Let us define a cluster $C\in\mathcal{C}^{*}$ to be
_irreducible from round $i$_, if $i$ is the minimum index such that
$\left|C\cap P_{i}\right|\leq 1$. Two central properties of the cluster
refinement due to Bateni et al. [BEFM21] are that after $\mathcal{O}(\log\log
n)$ rounds the size of each cluster in $\mathcal{C}^{*}$ reduces to
$\widetilde{\mathcal{O}}(\log n)$, and that after that, the total number of
the points in the reducible clusters in $\mathcal{C}^{*}$ reduces after each
round by a constant factor, implying that another $\mathcal{O}(\log\log n)$
rounds suffice to ensure the desired number of centers (at most $k$ due to the
irreducible clusters and $o(k)$ due to the reducible clusters) and hence
$\tau=\mathcal{O}(\log\log n)$. This is then complemented by the analysis of
the quality of the refinements which guarantees that each new refinement adds
an additive term of $\mathcal{O}(\textsc{opt})$ to the cost of the solution,
giving in total a double logarithmic approximation ratio. They further gave a
sketch of the analysis to get an approximation ratio of
$\mathcal{O}(\log\log\log n)$.

In our paper we substantially improve the approximation factor to
$\mathcal{O}(\log^{*}n)$ by extending the framework in the following sense. We
show that, after $\mathcal{O}(\log\log n)$ rounds, the size of each cluster in
$\mathcal{C}^{*}$ reduces to $\widetilde{\mathcal{O}}(\log n)$ such that the
refinement in each round adds an additive error of
$\mathcal{O}(\frac{\textsc{opt}}{\log\log n})$ to the cost of the solution.
Then, we show that after additional $\mathcal{O}(\log\log\log n)$ rounds, the
sizes of _almost all_ (but not all) clusters in $\mathcal{C}^{*}$ reduce to a
$\widetilde{\mathcal{O}}(\log\log n)$ such that the refinement in each round
adds an additive error of $\mathcal{O}(\frac{\textsc{opt}}{\log\log\log n})$
to the cost of the solution. Next, we show that after another
$\mathcal{O}(\log\log\log\log n)$ rounds, the sizes of _almost all_ clusters
in $\mathcal{C}^{*}$ reduce to a $\widetilde{\mathcal{O}}(\log\log\log n)$
such that the refinement in each round adds
$\mathcal{O}(\frac{\textsc{opt}}{\log\log\log\log n})$ to the cost of the
solution, and so on. We continue this until the sizes of almost all clusters
in $\mathcal{C}^{*}$ reduce to $\mathcal{O}(\log^{*}n)$. Observe that the
total number of rounds taken so far is bounded by $\mathcal{O}(\log\log n)$,
and we can argue that the current solution has an approximation ratio of
$\mathcal{O}(\log^{*}n)$. An important challenge in analyzing this approach is
that _not all clusters satisfy these size guarantees with high probability_.
Indeed, we cannot obtain a high probability guarantee by cluster refinement
relying on random sampling of the already small clusters; we can ensure only
that _most of the clusters are getting small_. Let
$\mathcal{C}^{**}\subseteq\mathcal{C}^{*}$ be the clusters that satisfy the
reduction property as discussed above, that is, such that the number of points
in each cluster of $\mathcal{C}^{**}$ is bounded by $\mathcal{O}(\log^{*}n)$
currently. We argue that the total number of points in the reducible clusters
in $\mathcal{C}^{**}$ reduces by a constant factor after each successive
round, adding an additive error of $\mathcal{O}(\textsc{opt})$ each time. This
implies that another $\mathcal{O}(\log(\log^{*}n))$ rounds are good enough to
ensure that we have the desired number of centers at the end. To bound the
total number of centers, we also need to show that the number of centers in
clusters in $\mathcal{C}^{*}\setminus\mathcal{C}^{**}$ (that is, the set of
clusters which fail to adhere to a size guarantee at some point during the
algorithm) is bounded. Note that we cannot _track_ which clusters succeed or
fail (doing so would require us to know an optimal clustering), and so we use
$\mathcal{C}^{*}$ and $\mathcal{C}^{**}$ only for the analysis. In summary,
the approach sketched above will reduce the number of clusters to $k(1+o(1))$,
and will ensure that the total number of rounds spent by our algorithm is
$\mathcal{O}(\log\log n)$ and the approximation ratio of our solution is
$\mathcal{O}(\log^{*}n)$. A more detailed overview is in Section 2.

Our approach relies heavily on the use of LSH (locality sensitive hashing),
and we provide a flexible implementation of LSH in MPC which one can configure
with an appropriate parameter $\rho$. Reducing the value of $\rho$ decreases
the amount of global space used by the algorithm (global space used is
$\widetilde{O}(n^{1+\rho})$) while increasing the approximation ratio.

###  1.3 Notation and preliminaries

We now introduce the notation used through the paper.

First, we present the setting of the parameters of our MPC. The $k$-center
algorithm in this paper works for any local space
${\mathrm{s}}=\mathcal{O}(n^{\delta})$ for a constant $0<\delta<1$: the
setting of $\delta$ has only a constant factor impact on the running time.
Similarly, the MPC can have any global space
${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\rho})$ for some constant $\rho>0$:
$\rho$ can be made arbitrarily small, and its setting has a constant factor
impact on the approximation ratio. We sometimes refer to MPC with these
choices of ${\mathrm{s}}$ and ${\mathrm{g}}$ simply as “MPC” in the rest of
this paper.

Let us recall that certain operations, particularly sorting and prefix sum of
$n$ elements, and broadcasting a value of size $<{\mathrm{s}}$, can be
computed deterministically in $O(1)$ rounds (see [GSZ11]).

The input to our problem is a set $P$ of $n$ points in $\mathbb{R}^{d}$, where
$d$ is a constant, and an integer parameter $k<n$. We define $d(p,q)$ as the
Euclidean distance between points $p$ and $q$ in $\mathbb{R}^{d}$. We
generalize this notation to the distance between a point and a set:
$d(p,S):=\min\limits_{q\in S}d(p,q)$ is the minimum distance from $p$ to a
point in $S$. We define $\textsc{cost}(P,S):=\max\limits_{p\in P}d(p,S)$ as
the distance of the point in $P$ which is “furthest away” from any point in
$S$. Without loss of generality, we assume that the input set is re-scaled so
that the minimum distance between any two points in $P$ is $1$; then we let
$\Delta$ to be the maximum distance between any two points in $P$.

We denote the set $\\{1,\ldots,t\\}$ by $[t]$ and
$\log^{(i)}n:=\underbrace{\log\dots\log}_{i}n$ the iterated logarithm of $n$.
By convention $\log^{(0)}n:=n$. The notations $\widetilde{\mathcal{O}}(f)$ and
$\widetilde{\Theta}(f)$ hide polynomial factors in $\log f$.

We now define formally the $k$-center clustering problem.

######  Definition 1.2.

Let $P$ be a set of points in $\mathbb{R}^{d}$. A _clustering_ $\mathcal{C}$
of $P$ is a partition of $P$ into nonempty clusters $C_{1},\ldots,C_{t}$. The
_radius_ of cluster $C_{i}$ is $\min\limits_{x\in C_{i}}\max\limits_{y\in
C_{i}}d(x,y)$, and the _cost_ of the clustering $\mathcal{C}$ is the maximum
of the radii of the clusters $C_{1},\ldots,C_{t}$.

######  Definition 1.3 ($k$-center clustering problem).

Let $k,n,d\in\mathbb{N}$ with $k\leq n$, and $P$ be a set of $n$ points in
$\mathbb{R}^{d}$. The $k$-center problem for $P$ is to find a set
$S^{*}\subseteq P$ such that

$S^{*}=\operatorname*{arg\,min}\limits_{S\subseteq
P:\left|S\right|=k}\textsc{cost}(P,S).$

Moreover, $\textsc{cost}(P,S^{*})$ is defined as the (optimal) cost of the
$k$-center problem for $P$.

We assume throughout the paper that $k>{\mathrm{s}}$. However, our algorithms
work as described provided that $k=\Omega((\log n)^{c})$ for a suitable
constant $c$ (which is also the main focus of the work).

###  1.4 Our results — detailed bounds

We now present in details the main result of this paper:

######  Theorem 1.4 (Main result).

Let $P$ be any set of $n$ points in $\mathbb{R}^{d}$ and let opt denote the
optimal cost of the $k$-center clustering problem for $P$. There exists an MPC
algorithm that in ${\mathcal{O}}(\log\log n)$ rounds determines with high
probability a set $T\subseteq P$ of $k+o(k)$ centers, such that
$\textsc{cost}(P,T)=\mathcal{O}(\log^{*}n)\cdot\textsc{opt}$. The MPC uses
local space ${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global space
${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\rho}\cdot\log^{2}\Delta)$.

1.4 follows directly from a more general theorem.

######  Theorem 1.5 (Generalization of 1.4).

Let $\alpha$ be an arbitrary integer, $1\leq\alpha\leq\log^{*}n-c_{0}$ for
some suitable constant $c_{0}$. Let $P$ be any set of $n$ points in
$\mathbb{R}^{d}$ and let opt denote the optimal cost of the $k$-center
clustering problem for $P$. There exists an MPC algorithm that in
${\mathcal{O}}(\log\log n)$ rounds determines with high probability a set
$T\subseteq P$ of centers, such that
$\textsc{cost}(P,T)=\mathcal{O}((\alpha+\log^{(\alpha+1)}n))\cdot\textsc{opt}$
and $\left|T\right|\leq
k\cdot\left(1+\frac{1}{\widetilde{\Theta}(\log^{(\alpha)}n)}\right)+\widetilde{\Theta}((\log^{(\alpha)}n)^{3})$.
The MPC uses local space ${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global
space ${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\rho}\cdot\log^{2}\Delta)$.

Observe that in 1.5 we have $\left|T\right|=k+o(k)$, since we are assuming
$k=\Omega((\log n)^{c})$ for some suitable constant $c$.

Let $\alpha_{0}$ be the solution to the equation $\alpha=\log^{(\alpha+1)}n$;
observe that $\alpha_{0}=\Theta(\log^{*}n)$. Then 1.4 is a corollary of 1.5
when we choose $\alpha=\alpha_{0}$.

1.5 can be seen as a fine-grained version of 1.4: as $\alpha$ increases the
cost of the solution decreases and number of center increases (with the number
of rounds always being $O(\log\log n)$). Therefore 1.5 is more amiable in
practical scenarios in the following sense: $\alpha$ in 1.5 can be set to
trade off between the quality of the solution and the number of centers in the
solution. We would also like to highlight that the result of Bateni et al.
[BEFM21] is a special case of 1.5 when $\alpha=1$ and $\alpha=2$ to obtain
$\mathcal{O}(\log\log n)$ and $\mathcal{O}(\log\log\log n)$ approximation,
respectively.

###  1.5 Organization of the paper

In Section 2 we give a proof of our main result predicated on the correctness
of our main algorithm, and then give an overview of the subroutines which our
main algorithm contains. In Section 3 we explain how LSH (locality-sensitive
hashing) on MPC can be implemented to assign each point $p\in P$ to a hub in
$H\subseteq P$ which is within a constant factor of the closest hub to $p$. In
Sections 4 and 5 we prove critical properties of subroutines used in our main
algorithm, and then in Section 6 we prove the correctness of our main
algorithm. Finally, Section 7 contains some conclusions.

##  2 Technical overview

Recall that 1.4 is our main result and 1.5 is its parameterized
generalization. Our proof of 1.5 (and hence of 1.4) relies on the following
main technical theorem.

######  Theorem 2.1 (Main technical theorem proved in this paper).

Let $\alpha$ be an arbitrary integer, $1\leq\alpha\leq\log^{*}n-c_{0}$ for
some suitable constant $c_{0}$. Let $r$ be an arbitrary positive real. Let $P$
be any set of $n$ points in $\mathbb{R}^{d}$ and let $\mathcal{C}_{r}$ be a
clustering of $P$ that has the minimum number of centers among all clusterings
of $P$ with cost at most $r$ and $\left|\mathcal{C}_{r}\right|=\Omega((\log
n)^{c})$ for a suitable constant $c$. There exists an MPC algorithm
Ext-$k$-Center (Algorithm 5) that with probability at least
$1-\frac{1}{(\log^{(\alpha-1)}n)^{\Omega(1)}}$, in ${\mathcal{O}}(\log\log n)$
rounds determines a set $T\subseteq P$ of centers, such that
$\textsc{cost}(P,T)=\mathcal{O}(r\cdot(\alpha+\log^{(\alpha+1)}n))$ and
$\left|T\right|\leq\left|\mathcal{C}_{r}\right|\cdot\left(1+\frac{1}{\widetilde{\Theta}(\log^{(\alpha)}n)}\right)+\widetilde{\Theta}((\log^{(\alpha)}n)^{3})$.
The MPC uses local space ${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global
space ${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\rho}\cdot\log\Delta)$.

Algorithm Ext-$k$-Center used in 2.1 takes two parameters: an accuracy
parameter $\alpha$ and a cost parameter $r$, and produces the output in a form
similar to that required in 1.5, except that the number of clusters is equal
to the number of centers in an optimal clustering of $P$ with cost at most
$r$. This is in contrast with a standard clustering setting where the number
of clusters is given as input, with no relationship to the cost of the
solution. Therefore, if we knew a constant factor approximation to the optimal
cost to the $k$-center problem, then setting it to be $r$ in 2.1, we would get
a desired solution as required in 1.5. This naturally suggests to run
Ext-$k$-Center multiple times in parallel in order to obtain 1.5. Note that
the success probability of 2.1 is not high. Hence we first run Ext-$k$-Center
a suitable number of times in parallel to get an algorithm $\mbox{{\sc
Ext}-$k$-{\sc Center}}^{\prime}$ whose output and space requirements are same
as that of Ext-$k$-Center, but the success probability is high. Then we run
$\mbox{{\sc Ext}-$k$-{\sc Center}}^{\prime}$ for $O(\log\Delta)$ choices of
$r$ (starting with $r=\Delta$ and decreasing a constant factor each time) in
parallel to get algorithm $\mbox{{\sc Ext}-$k$-{\sc Center}}^{\prime\prime}$
(the algorithm of 1.5). Moreover, $\mbox{{\sc Ext}-$k$-{\sc
Center}}^{\prime\prime}$ reports the output of $\mbox{{\sc Ext}-$k$-{\sc
Center}}^{\prime}$ for the minimum $r$ for which we get the number of centers
equals to $k+o(k)$. The details are in Appendix B.

###  2.1 Overview of the proof of 2.1

The idea to prove 2.1 is based on the framework which we call _locally
sensitive sampling_. We generate a set $H\subseteq P$ of points (called
_hubs_) by sampling each point in $P$ independently with a _suitable_
probability, and assign all other points to one of the hubs based on its
_locality_. Let $B_{h}$ be the _bag of the hub $h$_—-the set of points
associated to a hub $h\in H$. We run a variation of a well known greedy
algorithm [Gon85] (for $k$-center in the sequential setting) for each bag in
parallel to find a set of intermediate centers $C_{h}$ for hub $h$ such that
$\textsc{cost}(B_{h},C_{h})=\mathcal{O}(r)$. We again repeat the procedure by
setting $\bigcup_{h\in H}C_{h}$ as the point set. We continue this process a
particular number of times with a particular choice of probability and radius
parameters, and report the centers, at that point of time, as the final
solution.

This framework was recently used by Bateni et al. [BEFM21] to give an
$\mathcal{O}(\log\log n)$-round MPC algorithm with local space
${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global space
${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\delta})$, which computes an
$\mathcal{O}(\log\log\log n)$-approximate solution to $k$-center with
$k(1+o(1))$ centers, with high probability. We extend their framework and
generalize the analysis to give an $\mathcal{O}(\log^{*}n)$ approximate
solution as stated in 1.4. Note that 2.1 takes care of 1.4 via 1.5.

The algorithm corresponding to 2.1 is Ext-$k$-Center (Algorithm 5 in Section
6). Before describing Ext-$k$-Center, we describe and contextualize the three
subroutines which it uses (Nearest-Hub-Search, Sample-And-Solve and Uniform-
Center). The main algorithm of Bateni et al. [BEFM21] uses subroutine Sample-
And-Solve and Uniform-$k$-center. We use analogous subroutines Sample-And-
Solve and Uniform-Center in our algorithm corresponding to Sample-And-Solve
and Uniform-$k$-center in Bateni et al. [BEFM21], respectively, to achieve the
desired result. But there are some differences which we will discuss when we
describe Sample-And-Solve and Uniform-Center. Due to our implementation of
Nearest-Hub-Search, we are able to give a more flexible bound on global space.
We can improve the approximation ratio mainly due to generalizing their
Uniform-$k$-Center to Uniform-Center in our case and using sophisticated
analysis in our main algorithm that calls Uniform-Center.

Let us discuss first at a high level what these subroutines achieve in the
context of the framework of locally sensitive sampling (discussed at the
beginning of this section). Intuitively, the purpose of Sample-And-Solve is to
sparsify dense regions of points: it samples nodes with a given probability
and iteratively adds centers in order to ensure that the cost of the centers
remains low. Uniform-Center repeatedly uses Sample-And-Solve: its main purpose
is to guarantee that the number of centers in each cluster of some fixed
optimal clustering decreases in a certain way over time.

####  Nearest-Hub-Search ($Q,H$)

Takes as input a set $Q$ of at most $n$ points and a set of hubs $H\subseteq
Q$. For all points $q\in Q\setminus H$, it finds a point $\mbox{close}(q)\in
H$ such that $d(q,\mbox{close}(q))=\mathcal{O}(d(q,H))$, with probability at
least $1-\frac{1}{n^{\Omega(1)}}$. Nearest-Hub-Search can be implemented in
MPC with local space ${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global space
${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\rho}\cdot\log\Delta)$ in
$\mathcal{O}(1)$ rounds. Nearest-Hub-Search uses _locally sensitive hashing_
[HIM12] and its implementation in MPC. For details on Nearest-Hub-Search, see
Section 3.

####  Sample-And-Solve ($Q,p,r$)

Takes a set of $Q$ of at most $n$ points, a sampling parameter $p$, and a
radius parameter $r$. It produces some set of centers $S\subseteq Q$ such that
$\textsc{cost}(Q,S)=\mathcal{O}(r)$.444The constant inside
$\mathcal{O}(\cdot)$ depends on $\rho.$ Importantly, this can be implemented
in an MPC with local space ${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global
space $\widetilde{\mathcal{O}}(n^{1+\rho}\cdot\log\Delta)$ in $\mathcal{O}(1)$
rounds (4.1) as, aside from using Nearest-Hub-Search to assign points to hubs,
the computation is all done locally. Sample-And-Solve first samples each point
in $Q$ (independently) with probability $p$: let $H\subseteq Q$ be the set of
sampled points called hubs. Then Sample-And-Solve calls Nearest-Hub-Search
with input point set $Q$ and hub set $H$. After getting $\mbox{close}(q)$ for
each $q\in Q\setminus H$, Sample-And-Solve collects all points $B_{h}\subseteq
Q$ assigned to a hub $h\in H$ (including hub $h$) and selects a set of centers
$C_{h}$ from $B_{h}$ greedily using a variation of the sequential algorithm of
[Gon85], such that $\textsc{cost}(B_{h},C_{h})=\mathcal{O}(r)$. Finally, the
algorithm outputs $S=\bigcup_{h\in H}C_{h}$. However, there is a difficulty to
overcome: note that $\left|B_{h}\right|$ may be $\omega(n^{\delta})$. So
$B_{h}$ may not fit into the local memory of a machine. We show that this can
be handled by distributing the points in $B_{h}$ into multiple machines,
duplicating $h$ across all such machines. See Section 4 for more details about
Sample-And-Solve.

Algorithm Sample-And-Solve in our paper serves essentially the same purpose as
the corresponding algorithm due to Bateni et al. [BEFM21]. The approximation
guarantee and number of rounds performed are the same in both cases. However,
the global space used by our algorithm Sample-And-Solve is more flexible in
the following sense: reducing the value of $\rho$ decreases the amount of
global space used by the algorithm (global space used is
$\widetilde{\mathcal{O}}(n^{1+\rho})\cdot\log\Delta$) while increasing the
approximation ratio.

####  Uniform-Center $(V_{t},r,t)$

Takes a set $V_{t}$ of at most $n$ points, a radius parameter $r$, and an
additional parameter $t\leq n.$ It produces a set $S$ of centers, by calling
Sample-And-Solve $\tau=\Theta(\log\log t)$ times. $S_{i-1}$ is the input to
the $i$-th call and $S_{i}$ is the output of the $i$-th call: overall we have
$S_{0}=V_{t}$ and $S_{\tau}=S$ (the output of Uniform-Center). The probability
and radius parameters to the calls to Sample-And-Solve are set _suitably_.
From the guarantees we have from Sample-And-Solve, we have the following
guarantee for Uniform-Center: (i) it can be implemented in an MPC with local
space ${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global space
${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\rho}\cdot\log\Delta)$ in
$\mathcal{O}(\log\log t)$ rounds (5.1), and (ii)
$\textsc{cost}(V_{t},S)=\mathcal{O}(r\cdot\tau)=\mathcal{O}(r\log\log t)$
(5.2). Uniform-Center guarantees a reduction in cluster sizes in an optimal
clustering in the following sense. Consider a fixed clustering
$\mathcal{C}_{r}^{t}$ of $V_{t}$ that has cost at most $r$. For
$C\in\mathcal{C}_{r}^{t}$: if $\left|C\cap V_{t}\right|\leq t$, then
$\left|C\cap S\right|=\mathcal{O}(\log t\cdot(\log\log t)^{2})$, with
probability at least $1-\frac{1}{t^{\Omega(1)}}$. This is formally stated in
5.3: note that this ceases to be high probability when $t\in o(n)$. This
guarantee on the size reduction plays a crucial role when proving the number
of centers reported by Ext-$k$-Center in Section 6. For more details on
Uniform-Center, see Section 5.

Our Uniform-Center is a full generalization of the analagous
Uniform-$k$-center in Bateni et al. [BEFM21]. In particular,
Uniform-$k$-Center is a special case of our Uniform-Center when $t=n$. This
generalization plays a crucial role in the correctness of Ext-$k$-Center when
we call Uniform-Center multiple times. Uniform-$k$-Center is not robust enough
to be called from Ext-$k$-Center multiple times to achieve the desired result.

####  Ext-$k$-Center

The algorithm consists of two phases, where Phase 1 consists of $\alpha$
subphases and Phase 2 consists of $\beta={\Theta}(\log^{(\alpha+1)}n)$
subphases. In the $j$-th subphase of Phase 1, that is, in Phase 1.j,
Ext-$k$-Center calls $\mbox{{\sc Uniform}-{\sc
Center}}(T_{j-1},r_{j-1},t_{j-1})$, where $T_{0}=P$, $r_{0}=\frac{r}{\log\log
n}$, $t_{0}=n$, $t_{j}=\widetilde{\Theta}(\log^{(j)}n),$ and
$r_{j}=\frac{r}{\log\log t_{j}}$. Observe that the guarantees of Uniform-
Center ensure the following:

  1. (i)

Phase 1 can be implemented in an MPC with local space
${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global space
${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\rho}\cdot\log\Delta)$ in
$\sum\limits_{j=1}^{\alpha}\log\log t_{j-1}=\mathcal{O}(\log\log n)$ rounds;

  2. (ii)

$\textsc{cost}(T_{j-1},T_{j})=\mathcal{O}(r_{j-1}\log\log
t_{j-1})=\mathcal{O}(r)$ for each $j\in[\alpha]$. Hence,
$\textsc{cost}(P,T_{\alpha})=\mathcal{O}(r\alpha)$.

Now consider Phase 2 of Ext-$k$-Center.

In the $i$-th subphase of Phase 2, that is Phase 2.i, Ext-$k$-Center calls
$\mbox{{\sc Sample-And-Solve}}(T_{\alpha+i-1},\frac{1}{2},r)$, where
$T=T_{\alpha+\beta}$ is the final output of Ext-$k$-Center. From the guarantee
of Sample-And-Solve, we have

  1. (i)

Phase 2 can be implemented in an MPC with local space
${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global space
${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\delta}\cdot\log\Delta)$ in
$\mathcal{O}(\beta)=\mathcal{O}(\log^{(\alpha+1)}n)$ rounds;

  2. (ii)

$\textsc{cost}(T_{\alpha+i-1},T_{\alpha+1})=\mathcal{O}(r)$ for each
$i\in[\beta]$. Hence,

$\displaystyle\textsc{cost}(P,T)$
$\displaystyle=\textsc{cost}(P,T_{\alpha+\beta})=\textsc{cost}(P,T_{\alpha})+\mathcal{O}(\beta
r)$ $\displaystyle=\mathcal{O}(r\cdot(\alpha+\log^{(\alpha+1)}n))\enspace.$

Combining the guarantees concerning the round complexity, global space and
approximation guarantee of Phase 1 and Phase 2, we get the claimed guarantees
on round complexity, global space and approximation guarantees in 2.1 (see 6.1
for round and global space guarantee and 6.2 for the guarantee on
approximation factor).

Now, we discuss how we bound the number of centers that Ext-$k$-Center
outputs, that is, $\left|T\right|$. Consider an optimal clustering
$\mathcal{C}_{r}$ of $P$ with cost at most $r$. A cluster
$C\in\mathcal{C}_{r}$ is said to be _active_ (after Phase 1) if $\left|C\cap
T_{j}\right|\leq t_{j}$ for each $j$ with $1\leq j\leq\alpha$. We say $C$ is
_inactive_ , otherwise. Using the guarantee given by Uniform-Center concerning
the reduction in cluster sizes, we can show that the total number of centers
in $T_{\alpha}$, that are in inactive clusters, is
$\mathcal{O}\left(\frac{\left|\mathcal{C}_{r}\right|}{(\log^{(\alpha)}n)^{\Omega(1)}}\right)$,
with probability at least
$1-\sum\limits_{i=1}^{\alpha}\frac{1}{t_{i-1}^{\Omega(1)}}$ (see 6.6). Note
that $T_{\alpha}$ denotes the set of intermediate centers we have after Phase
1. So, for any cluster $C\in\mathcal{C}_{r}$ that is active after Phase 1, it
satisfies $\left|C\cap T_{\alpha}\right|\leq
t_{\alpha}=\widetilde{\Theta}{(\log^{(\alpha)}n)}$. That is, with probability
at least $1-\sum\limits_{i=1}^{\alpha}\frac{1}{t_{i-1}^{\Omega(1)}}$, we have
the following:

$\displaystyle\left|T_{\alpha}\right|$
$\displaystyle\leq\left|\mathcal{C}_{r}\right|\cdot
t_{\alpha}+\mathcal{O}\left(\frac{\left|\mathcal{C}_{r}\right|}{(\log^{(\alpha)}n)^{\Omega(1)}}\right)\enspace.$

We define an active cluster $C\in\mathcal{C}_{r}$ is $i$-large if $\left|C\cap
T_{\alpha+i-1}\right|\geq 2$. We show that the total number of intermediate
centers in any large clusters reduces by a constant factor in Phase 2.i, with
probability at least $1-\frac{1}{t_{\alpha-1}^{\Omega(1)}}$. Note that the
total number of intermediate centers in all active large clusters, just before
Phase 2, is at most $\left|\mathcal{C}_{r}\right|\cdot
t_{\alpha}=\left|\mathcal{C}_{r}\right|\cdot\widetilde{\Theta}(\log^{(\alpha)}n)$,
and we are executing $\beta={\Theta}(\log^{(\alpha+1)}n)$ many sub-phases in
Phase 2. We can show that the total number of centers in the active large
clusters, after Phase 2, is at most
$\frac{\left|\mathcal{C}_{r}\right|}{\widetilde{\Theta}(\log^{(\alpha)}n)}+\widetilde{\Theta}((\log^{(\alpha)}n)^{3})$,
with probability at least $1-\frac{1}{t_{\alpha-1}^{\Omega(1)}}$ (6.7).
Combined with the fact the number of active small clusters can be at most
$\left|\mathcal{C}_{r}\right|$ with the bound on number of inactive clusters
in Phase 2, we have the desired bound on $\left|T\right|$. Full details of
Ext-$k$-Center and its analysis are presented in Section 6.

##  3 Nearest Hub Search

Recall that our Nearest-Hub-Search algorithm takes a set $Q$ of points and a
set $H\subseteq Q$ of hubs. For each $q\in(Q\setminus H)$, we want to find a
hub $h\in H$ such that the distance between $q$ and $h$ is only a constant-
factor more than the distance between $q$ and the closest hub to $q$ in $H$:
informally, $h$ is “almost” the closest hub to $q$ in $H$.

In this section, we use _locally sensitive hashing_ (LSH) [HIM12] to implement
algorithm Nearest-Hub-Search ($Q,H$) on MPC. Our implementation of locally
sensitive hashing is parameterizable: by setting the parameter $\rho$
appropriately, one can reduce the global space while increase the
approximation ratio, or vice versa.

First, we begin by recalling the definition of locally sensitive hashing,
introduced in [HIM12]:

######  Definition 3.1 (Locally sensitive hashing [HIM12]).

Let $r\in\mathbb{R}^{+}$, $c>1$ and $p_{1},p_{2}\in(0,1)$ be such that
$p_{1}>p_{2}$. A hash family $\mathcal{H}=\\{h:\mathbb{R}^{d}\rightarrow U\\}$
is said to be a $(r,cr,p_{1},p_{2})$-LSH family if for all
$x,y\in\mathbb{R}^{d}$ the following hold:

  * •

If $d(x,y)\leq r$, then $\mbox{Pr}_{h\in\mathcal{H}}(h(x)=h(y))\geq p_{1}$;

  * •

If $d(x,y)\geq cr$, then $\mbox{Pr}_{h\in\mathcal{H}}(h(x)=h(y))\leq p_{2}$.

Consider the following proposition that talks about the existence of a
particular hash family, which will be useful to describe and analyse Nearest-
Hub-Search ($Q,H$) in Algorithm 1.

######  Proposition 3.2 ([HIM12]).

Let $r,n\in\mathbb{N}$ and $\rho\in(0,1)$. There exists a
$(r,c_{\rho}r,(1/n)^{\rho},1/n)$-LSH family, where $c_{\rho}$ is a constant
depending only on $\rho$.

In Nearest-Hub-Search ($Q,H$), $Q$ is a set of at most $n$ points and
$H\subseteq Q$ is the set of hubs. Our objective is to find a hub for each
point which is at most some constant factor further away than the nearest hub,
rather than finding the hub which is the closest. We do this by making
$\log\Delta$ guesses about the distance to the nearest hub, and for each guess
trying to find a hub within that distance.

For our $\log\Delta$ guesses for $r$ (the distance to the closest hub), we
take (independently and uniformly at random) $L=\Theta(n^{\rho})$ many hash
functions from a $(r,c_{\rho}r,(1/n)^{\rho},1/n)$-LSH family and use them to
hash all the points, including the hubs.555The constant $\rho$ is the same
constant as in the exponent of $n$ in the global space bound. Recall our
tradeoff: choosing a smaller $\rho$ decreases the amount of global space
needed, but increases the approximation ratio. Then we gather all points with
the same hash value on consecutive machines. We then need to find, for each
point, a hub that is close to it. This is difficult if the number of hubs
mapped to a given hash value is large: if $h$ hubs and $m$ points are mapped
to the same hash value, then we have to perform $h\cdot m$ distance checks,
which is potentially prohibitive if $h\cdot m>{\mathrm{s}}$. To overcome this
we show that, if many hubs are mapped to the same hash-value, we are able to
discard all but a constant number of them, and retain for each point a hub
that is within a constant factor of the distance of the closest hub. This
works because of the choice of our hash function and by the definition of LSH.
The full algorithm Nearest-Hub-Search ($Q,H$) is described in Algorithm 1, and
its correctness is proved in 3.3.

######  Lemma 3.3 (Nearest hub search).

Let $Q$ be a set of at most $n$ points in $\mathbb{R}^{d}$, $H\subseteq Q$
denote the set of hubs, and $c_{\rho}$ be a suitable constant depending on
$\rho$. There exists an MPC algorithm Nearest-Hub-Search ($Q,H$) (as described
in Algorithm 1) that with high probability, in $\mathcal{O}(1)$ rounds, for
all $q\in Q\setminus H$, finds a hub $\mbox{close}(q)\in H$ such that
$d(q,\mbox{close}(q))<2c_{\rho}\cdot d(q,H)$. The MPC uses local space
${\mathrm{s}}=O(n^{\delta})$ and global space
${\mathrm{g}}=\mathcal{O}(n^{1+\rho}\cdot\log^{2}n\cdot\log\Delta)$.

Input: A set $Q$ of at most $n$ points and a set of hubs $H\subseteq Q$.

Output: For each point in $Q$, report $\mbox{close}(p)\in H$ such that
$d(p,\mbox{close}(p))\leq 2c_{\rho}\cdot d(p,H)$, where $c_{\rho}$ is a
suitable constant depending only on $\rho$.

1 begin

2 for  _( $i=1$ to $I=\Theta(\log n)$)_ do

3 for  _(j=0 to $\log\Delta$)_ do

4 Set $r=2^{j}$

5 Take $L=\Theta(n^{\rho})$ many hash function $f_{1},\ldots,f_{L}$
(independently and uniformly at random) from a
$(r,c_{\rho}r,(1/n)^{\rho},1/n)$-LSH family.

6 for  _( $\ell=1$ to $L$)_ do

7 Determine $f_{\ell}(q)$ for each $q\in Q$.

8 Find the distance of each $q\in Q$ with at most a constant (say $10$) number
of hubs $h\in H$ such that $f_{l}(q)=f_{l}(h)$. If we get such a $h\in H$ such
that $d(q,h)\leq c_{\rho}\cdot r$, then we set $\mbox{close}_{ij\ell}(q)=h$
and null, otherwise.

9 end for

10 Set $\mbox{close}_{ij}(q)=\mbox{{\sc null}}$ if
$\mbox{close}_{ij\ell}(q)=\mbox{{\sc null}}$ for all $\ell\in[L]$. Otherwise,
set $\mbox{close}_{ij}(q)=\mbox{close}_{ij\ell}(q)$ for some $\ell\in L$.

11 end for

12

13 Set $\mbox{close}_{i}(q)=\mbox{{\sc null}}$ if
$\mbox{close}_{ij}(q)=\mbox{{\sc null}}$ for all $j\in[\log\Delta]$.
Otherwise, $\mbox{close}_{i}(q)=\mbox{close}_{ij^{*}}(q)$ such that $j^{*}$ is
minimum among all $j$ for which $\mbox{close}_{ij}(q)$ is not null.

14 end for

15 If there exists a $q\in Q$ such that $\mbox{close}_{i}(q)$ is null for all
$i\in[\log n]$, then report Fail.

16 Otherwise, set $\mbox{close}(q)=\mbox{close}_{i}(q)$ for some $i\in I$.

17 end

18

Algorithm 1 Nearest-Hub-Search ($Q,H$)

From Algorithm 1, note that we repeat a procedure (lines 3–12 that find an
almost closest hub with probability $2/3$) $I=\Theta(\log n)$ times, and
report the output we get from any of the instances. Consider 3.4, that says
that, in Nearest-Hub-Search each point $q\in Q$ finds $\mbox{close}(q)\in H$
satisfying the required property with high probability. This will immediately
imply the correctness of 3.3. We then discuss the MPC implementation of
Nearest-Hub-Search.

Note that $\mbox{close}_{i}(q)$ (which is either null or a point in $H$ such
that $d(q,\mbox{close}_{i}(q))=O(d(q,H))$) denotes the output of Nearest-Hub-
Search for point $q\in Q\setminus H$ and the instance $i\in I$.

######  Lemma 3.4.

For a particular $q\in Q\setminus H$ and $i\in I$, $\mbox{close}_{i}(q)\in H$
is not null and $d(q,\mbox{close}_{i}(q))\leq 2c_{\rho}\cdot d(q,H)$, with
probability at least $2/3$.

###### Proof.

Consider $j^{*}$ such that $d(q,H)\leq r=2^{j^{*}}\leq 2\cdot d(q,H)$, and
$q_{h}\in H$ be such that $d(q,q_{h})\leq 2\cdot d(q,H)$. As each $f_{i},i\in
L,$ is a function chosen from $(r,c_{\rho}r,(1/n)^{\rho},1/n)$-LSH family,
$\mbox{Pr}(f_{i}(q)=f_{i}(q_{h}))\geq\frac{1}{n^{\rho}}$. As
$L=\Theta(n^{\rho})$, there exists an $\ell^{*}\in L$ such that
$f_{\ell^{*}}(q)=f_{\ell^{*}}(q_{h})$ with probability at least $9/10$. But
our algorithm may not find this particular $q_{h}$ while considering the hubs
$h\in H$ such that $f_{\ell^{*}}(q)=f_{\ell^{*}}(q_{h})=f_{\ell^{*}}(h)$ (See
line 8 of Nearest-Hub-Search). Again, as $f_{\ell^{*}}$ is chosen from
$(r,c_{\rho}r,(1/n)^{\rho},1/n)$-LSH family, the expected number of hubs $h\in
H$, with $d(q,h)>c_{\rho}r$ but $f_{\ell^{*}}(q)=f_{\ell^{*}}(h)$, is at most
$1$. By Markov’s Inequality, the probability that the number of such hubs is
more than $10$ is at most $1/10$. So, with probability at least $2/3$,
Nearest-Hub-Search, sets $\mbox{close}_{ij^{*}\ell^{*}}=h$ for some $h\in H$
such that $d(q,h)\leq c_{\rho}r$, that is, $d(q,h)\leq 2c_{\rho}\cdot d(q,H)$.
Now considering the way we set $\mbox{close}_{ij}(q)$ from
$\mbox{close}_{ij\ell}(q)$’s ($\ell\in L$) in line 10 and
$\mbox{close}_{i}(q)$ from $\mbox{close}_{ij}(q)$’s $(0\leq j\leq\log\Delta)$
in line 12, we have that Nearest-Hub-Search sets $\mbox{close}_{i}(q)\in H$
such that $d(q,\mbox{close}_{i}(q))\leq 2c_{\rho}\cdot d(q,H)$ with
probability at least $2/3$. ∎

Now, consider the way Nearest-Hub-Search sets the value of $\mbox{close}(q)$
in lines 14–15 from $\mbox{close}_{i}(q)$’s. By 3.4, we have $\mbox{close}(q)$
such that it is not null and $d(q,\mbox{close}(q))\leq 2c_{\rho}\cdot d(q,H)$
with probability at least $1-\frac{1}{n^{\Omega(1)}}.$ This is because
$I=\Theta(\log n)$. Applying the union bound over all points in $Q\setminus
H$, we see that 3.3 is implied by 3.4, except the details of MPC
implementation.

###  MPC implementation of Nearest-Hub-Search

Without loss of generality, we assume that $\rho<\delta$ as otherwise we can
set $\rho=\delta$. First, notice that, if we can implement lines 4-10 of
Nearest-Hub-Search in MPC with local space
${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global space
${\mathrm{g}}=\mathcal{O}(n^{1+\rho}\cdot\log n)$, then we can run these lines
in parallel for each possible value of $i$ and $j$ (adding a factor of
$\mathcal{O}(\log n\cdot\log\Delta)$ to the global space). Then the results
can be aggregated in $\mathcal{O}(1)$ rounds using sorting and prefix sum
[GSZ11].

It suffices then to show that lines 4–10 of Nearest-Hub-Search can be
implemented in the desired rounds and space. The hash functions in line 5 can
be generated locally by some “leader” machine and broadcast to the other
machines in $O(1)$ rounds, since we assume $\rho<\delta$. We again perform
lines 6–9 in parallel, giving each $f\in L$ its own set of machines to use.

We next consider the implementation of lines 7–8 given a specific $f\in L$.
Machines can compute $f$ locally and without communication. Each point $q\in
Q$ is now represented by a tuple $(f(q),\text{hub}(q),q)$, where
$\text{hub}(q)=1$ if $q\in H$ and $0$, otherwise. Machines then sort these
tuples lexicographically and remove (using prefix sum) all but $10$ hubs for
each value in $\text{range}(f)$. For each $v\in\text{range}(f)$, we now have
to compute the distance between each point $q\in Q$ such that $f(q)=v$, and
each hub $h\in H$ such that $f(h)=v$ and $h$ was not removed. It might be the
case that some points in $Q$ are not located on the same machine as the hubs
which are hashed to the same value (and in general, these points might not all
fit on one machine, see discussion in Section 4). However, all that is
required in this case is that the hubs can be sent to all machines containing
points hashed to the same value: this can be done using prefix sum in a
constant number of rounds; since there are at most $10$ hubs for each value in
$\text{range}(f)$, each machine receives at most $10$ hubs. Now machines have
the information necessary to locally compute $\mbox{close}_{ij\ell}(q)$ for
all points that they contain, and for each point $q\in Q$ the tuple
$(q,\mbox{close}_{ij\ell}(q))$ is generated.

Finally, observe that line 10 can be implemented in $\mathcal{O}(1)$ rounds
using sorting and prefix sum.

##  4 Sample and Solve

In this section, we describe Sample-And-Solve $(Q,p,r)$, which is a subroutine
in Uniform-Center and Ext-$k$-Center in Sections 5 and 6, respectively.
Sample-And-Solve $(Q,p,r)$ takes a set $Q$ of at most $n$ points, a sampling
parameter $p$, and a radius parameter $r$, it relies on Nearest-Hub-Search
discussed in Section 3, and produces a set of centers $S\subseteq Q$ such that
$\textsc{cost}(Q,S)=\mathcal{O}(r)$.

Input: Set $R$ of at most $n$ points; radius parameter $r\in\mathbb{R}^{+}$.

Output: A set $G\subseteq R$ of centers.

1 begin

2 Set $G\leftarrow\\{h\\}$.

3 while  _( $\exists~{}x\in R$ with $d(x,G)=\min_{y\in R}d(x,y)>4c_{\rho}r$)_
do

4 //  Here $c_{\rho}$ is the constant as in 3.3.

5 Let $x\in R$ be the point furthest from $G$; add $x$ to $G$.

6 end while

7 Report the set $G$ of centers.

8 end

9

Algorithm 2 Greedy ($R,h,r$)

Input: Set $Q$ of at most $n$ points; probability parameter $p\in(0,1)$;
radius parameter $r\in\mathbb{R}^{+}$.

Output: A set $S\subseteq Q$ of centers.

1 begin

2 if  _$\left(\left|Q\right|\leq{\mathrm{s}}=\mathcal{O}(n^{\delta})\right)$_
then

3 Call $\mbox{{\sc Greedy}}(Q,q,r)$ for some arbitrary $q\in Q$, and report
the set of centers output by it as $S$.

4 end if

5

6 Sample each point in $Q$ independently with probability $p$. Points which
are sampled form the set of hubs $H$.

7 If $H=\emptyset,$ report Fail.

8 For each point $q$ in $Q$, assign it to the closest hub in $H$ by calling
$\mbox{{\sc Nearest-Hub-Search}}(Q,H,\rho)$. We call the set of points
assigned to a hub $h\in H$ the bag corresponding to $h$, and denote it as
$B_{h}$. Note that $B_{h}$ includes $h$.

9 for  _(each $h\in H$)_ do

10 if  _$(\left|B_{h}\right|\leq{\mathrm{s}})$_ then

11 Collect $B_{h}$ on a single machine.

12 $S_{h}\leftarrow\mbox{{\sc Greedy}}(B_{h},h,r)$.

13 end if

14 else

15 Form bags $B_{h_{1}},\ldots,B_{h_{w}}$, keeping $h$ in every $B_{h_{i}}$
($i\in[w]$) and putting other point in $B_{h}\setminus\\{h\\}$ into exactly
one of the $B_{h_{i}}$’s, such that
$\left|B_{h_{i}}\right|\leq{\mathrm{s}}=\mathcal{O}(n^{\delta})$ for each
$i\in[w]$.

16 $S_{h_{i}}\leftarrow\mbox{{\sc Greedy}}(B_{h_{i}},h,r)$, where $i\in[w]$.

17 $S_{h}\leftarrow\bigcup\limits_{i=1}^{w}S_{h_{i}}$.

18 end if

19

20 end for

21 Report set of centers $S=\bigcup\limits_{h\in H}S_{h}$.

22 end

23

Algorithm 3 Sample-And-Solve ($Q,p,r$)

Sample-And-Solve $(Q,p,r)$ calls algorithm Greedy $(R,h,r)$ as a subroutine,
which produces a set of centers $G\subseteq R$ such that
$\textsc{cost}(R,G)=\mathcal{O}(r)$. Greedy $(R,h,r)$ is a variation of a
classic 2-approximation algorithm for $k$-center in the sequential setting
[Gon85]. In Sample-And-Solve $(Q,p,r)$, the idea is to sample each point in
$Q$ (independently) with probability $p$ to form a set of hubs $H$. Then each
point $q\in Q$ will be assigned to some hub $h\in H$ by using Nearest-Hub-
Search (as described in Algorithm 1). For $h\in H$, let $B_{h}$ be the set of
points assigned to $h$ (including $h$ itself). We run Greedy for the points in
$B_{h}$, to produce a set of centers $S_{h}$. Finally, $\bigcup_{h\in H}S_{h}$
is the output reported by Sample-And-Solve. There are other technicalities –
$\left|B_{h}\right|$ may be much larger than ${\mathrm{s}}$. In that case, we
distribute the points in $B_{h}\setminus\\{h\\}$ across a number of machines,
but we send $h$ to each machine, ensuring that the total number of points
assigned to a machine (including $h$) is less than ${\mathrm{s}}$—and then we
apply Greedy to the points on each of these machines.

The formal algorithm for Sample-And-Solve is presented in Algorithm 3. The
approximation guarantee, round complexity and space complexity of Sample-And-
Solve are stated in 4.1. An additional property of Sample-And-Solve is stated
in 4.4 which will be useful in both Section 5 and Section 6.

######  Lemma 4.1 (Approximation guarantee, round complexity and space
complexity of Sample-And-Solve).

Consider Sample-And-Solve ($Q,p,r$), as described in Algorithm 3. With
probability at least $1-\min\left\\{e^{-\Omega\left(p\cdot
n^{\delta}\right)},\frac{1}{n^{\Omega(1)}}\right\\}$, it does not report Fail,
and moreover:

  1. (i)

It produces a set of centers $S\subseteq Q$ such that $\textsc{cost}(Q,S)\leq
4c_{\rho}r=\mathcal{O}(r)$, where $c_{\rho}$ is the constant as in 3.3;

  2. (ii)

It takes $\mathcal{O}(1)$ MPC rounds with local space
${\mathrm{s}}=\mathcal{O}\left(n^{\delta}\right)$ and global space
${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\rho}\cdot\log\Delta)$.

######  Remark 4.2.

We call Sample-And-Solve from Uniform-Center (Algorithm 4) with probability
parameter $p=\Omega\left(\frac{\log n}{n^{\delta}}\right)$. Therefore, the
success probability of Sample-And-Solve in our case is always at least
$1-\frac{1}{n^{\Omega(1)}}$.

###### Proof of 4.1.

Note that Sample-And-Solve (Algorithm 3) crucially calls subroutine Greedy
(Algorithm 2) multiple times, particularly in line numbers 2, 10 and 14. We
start the proof with the following observation (about algorithm Greedy
$(R,h,r)$) that follows from the description of Algorithm 2.

######  Observation 4.3.

The output $G\subseteq R$ produced by Greedy ($R,h,r$) (as described in
Algorithm 2) satisfies $\textsc{cost}(R,G)\leq 4c_{\rho}r$.

Note that both (i) and (ii) of 4.1 are direct if
$\left|Q\right|\leq{\mathrm{s}}$. As in that case, we executes $\mbox{{\sc
Greedy}}(Q,q,r)$ for some $q\in Q$ in one machine locally, and report its
output as $S$. By 4.3, we have $\textsc{cost}(Q,S)\leq 4c_{\rho}r$.

Now consider the case when $\left|Q\right|>{\mathrm{s}}$. Note that Sample-
And-Solve reports Fail only when the set of hubs $H$ is $\emptyset$. As every
point in $Q$ is added to $H$ with probability $p$ independently, the
probability that Sample-And-Solve reports Fail is at most
$\left(1-p\right)^{\left|Q\right|}\leq e^{-\Omega\left(p\cdot
n^{\delta}\right)}$. Now, we argue (i) and (ii) separately. Recall the
description of Algorithm 3 from Line 7–17.

  1. (i)

By 4.3, for $h\in H$, $\textsc{cost}(B_{h},S_{h})\leq 4c_{\rho}r$. As
$S=\bigcup\limits_{h\in H}S_{h}$ and $Q=\bigcup\limits_{h\in H}B_{h}$,
$\textsc{cost}(Q,S)\leq 4c_{\rho}r$.

  2. (ii)

From 3.3, Nearest-Hub-Search can be implemented in MPC with local space
${\mathrm{s}}=\mathcal{O}(n^{\delta})$ and global space
${\mathrm{g}}=\widetilde{\mathcal{O}}(n^{1+\rho}\cdot\log\Delta)$ in
$\mathcal{O}(1)$ rounds. After Nearest-Hub-Search is performed, each point
knows its assigned hub. Using sorting, we can place all points with the same
hubs on consecutive machines in $\mathcal{O}(1)$ rounds, and using prefix sum,
we can count the number of points assigned to each hub in $\mathcal{O}(1)$
rounds. Now, we consider two cases:

If $|B_{h}|\leq{\mathrm{s}}$ (that is: the bag could fit on a single machine)
then Greedy on $B_{h}$ can be performed on a single machine without
communication, that is, in $0$ rounds.666A minor technical matter is moving
$B_{h}$ to a single machine if it is big enough to fit but originally stored
on two consecutive machines. This can be done in $1$ round if we have $\geq
2{\mathrm{s}}/n$ machines: when sorting, use only the first ${\mathrm{s}}/n$
machines, then if $B_{h}$ was originally stored on machines $i$ and $i+1$,
move it to machine $i+{\mathrm{s}}/n$.

If $|B_{h}|>{\mathrm{s}}$ (that is: the bag could not fit on a single machine)
then we arbitrarily partition the bag and perform Sample-And-Solve on each
part. Specifically, we send $h$ to each of the consecutive machines on which
$B_{h}$ is stored, and these machines perform Greedy on the subset of the bag
that they hold locally. This can be performed in $\mathcal{O}(1)$ rounds.

∎

######  Lemma 4.4 (An additional guarantee of Sample-And-Solve).

Let $\mathcal{C}_{r}$ be a clustering of $Q$ having cost at most $r$. Then,
with high probability, the following holds for any $C\in\mathcal{C}_{r}$: if
at least one hub is selected from $C$, then no further point in $C\setminus H$
is selected as a center, that is, $\left|S\cap C\right|=\left|H\cap C\right|$.

###### Proof.

Consider any point $q\in C\setminus H$. As at least one hub is selected from
$C$, $d(q,H)\leq 2r$ . By the guarantee from Nearest-Hub-Search (see 3.3),
with probability at least $1-\frac{1}{n^{\Omega(1)}}$, $q$ is assigned to some
hub $h\in H$ such that $d(q,h)\leq 2c_{\rho}d(q,H)\leq 4c_{\rho}r$. So, when
we call Greedy ($B_{h},h,r$), as $d(q,h)\leq 4c_{\rho}r$, $q$ will not be
selected as a center. This implies that $\left|S\cap C\right|\leq\left|H\cap
C\right|$. The claim follows as $H\subseteq S$. ∎

##  5 Uniform Center algorithm

In this section, we describe Uniform-Center $(V_{t},r,t)$, which iteratively
refines a set of centers to a smaller set of centers, by calling Sample-And-
Solve on a quadratically-increasing probability schedule. It calls Sample-And-
Solve $\Theta(\log\log t)$ times. The $i$-th call to Sample-And-Solve is
Sample-And-Solve $(S_{i-1},p_{i-1},r)$ (in particular): it produces a set
$S_{i}\subseteq S_{i-1}$ of centers as the output, where $S_{0}=V_{t}$ and the
probability parameters are set suitably. The formal algorithm is described in
Algorithm 4. The round complexity, space complexity and approximation
guarantee are stated in Lemmas 5.1 and 5.2 — they follow from the guarantees
we have for Sample-And-Solve in 4.1 and the fact that Uniform-Center
$(V_{t},r,t)$ calls Sample-And-Solve $\mathcal{O}(\log\log t)$ times. Uniform-
Center has an additional guarantee as stated in 5.3 relating to the reduction
of cluster sizes, which plays a crucial role in proving the correctness of
Ext-$k$-Center in Section 6. In particular it is useful in bounding the number
of centers output by Ext-$k$-Center.

Input: A set of points $V_{t}$ of at most $n$ points, a radius parameter
$r\in\mathbb{R}^{+}$, and an additional parameter $t\leq n$.

Output: A set $S\subseteq V_{t}$ of centers.

1 begin

2

3 $p_{0}=\Theta\left(\frac{\log n}{n^{\delta}}\right)$, $s_{0}=t$, and
$S_{0}\leftarrow V_{t}$.

4 for  _ $i=1$ to $\tau=\Theta(\log\log t)$_ do

5

6 $S_{i}\leftarrow\mbox{{\sc Sample-And-
Solve}}\left(S_{i-1},p_{i-1},r\right).$

7 $s_{i}\leftarrow\sqrt{s_{i-1}}$ and $p_{i}=\frac{1}{s_{i}}$.

8 end for

9 Report $S=S_{\tau}$.

10 end

11

Algorithm 4 Uniform-Center ($V_{t},r,t$)

######  Lemma 5.1 (Round complexity and global space of Uniform-Center).

Consider Uniform-Center ($V_{t},r,t$), as described in Algorithm 4. The number
of rounds taken by the algorithm is $\mathcal{O}(\log\log t)$ and the global
space used by the algorithm is
${\mathrm{g}}=\widetilde{\mathcal{O}}\left(n^{1+\rho}\cdot\log\Delta\right)$.

###### Proof.

As Uniform-Center ($V_{t},r,t$) calls Sample-And-Solve $\mathcal{O}(\log\log
t)$ times, this follows directly from 4.1 (ii) . ∎

######  Lemma 5.2 (Approximation guarantee of Uniform-Center).

Consider Uniform-Center ($V_{t},r,t$) as described in Algorithm 4. It produces
output $S$ such that $\mbox{{\sc Cost}}(V_{t},S)=\mathcal{O}(r\cdot\log\log
t).$

###### Proof.

In the $i$-th iteration of $\mbox{{\sc Uniform}-{\sc Center}}(V_{t},r,t)$, we
call $\mbox{{\sc Sample-And-Solve}}\left(S_{i-1},p_{i-1},r\right)$, and get
$S_{i}$ as the centers. By 4.1 (i),
$\textsc{cost}(S_{i-1},S_{i})=\mathcal{O}(r)$, where $1\leq i\leq\tau$. Hence,

$\displaystyle\textsc{cost}(V_{t},S)$
$\displaystyle\leq\sum_{i=1}^{\tau}\textsc{cost}(S_{i-1},S_{i})=\tau\cdot\mathcal{O}(r)=\mathcal{O}(r\log\log
t)\enspace.\qed$

######  Lemma 5.3 (Reduction in cluster sizes).

Consider Uniform-Center ($V_{t},r,t$) as described in Algorithm 4, and a fixed
clustering $\mathcal{C}_{r}^{t}$ of $V_{t}$ that has cost $r$. It produces
output $S\subseteq V_{t}$ such that the following holds for any
$C\in\mathcal{C}_{r}^{t}$: if $\left|C\cap V_{t}\right|\leq t$, then with
probability at least $1-\frac{1}{t^{\Omega(1)}}$, we have $\left|C\cap
S\right|=\mathcal{O}\left(\log t\cdot(\log\log t)^{2}\right)$.

###### Proof.

Let $b_{i}=(1+\eta)^{i}s_{i}\log t\cdot\left(\log\log t\right)^{2}$, where $i$
is an non-negative integer and $\eta=\Theta\left(\frac{1}{\log\log t}\right)$.
Observe that

$b_{\tau-1}=\left(1+\eta\right)^{\tau-1}s_{\tau-1}\log t(\log\log
t)^{2}=\mathcal{O}\left(\log t\cdot\left(\log\log t\right)^{2}\right).$

Using induction on $i$ ($i\in\mathbb{N}$), we will show that $\left|C\cap
S_{i}\right|\leq b_{i-1}$ for each $i$ with $1\leq i\leq\tau$, with
probability at least $1-\frac{1}{t^{\Omega(1)}}$. This will imply the desired
result as $S_{i}$ is the output after the $i$-th iteration, and $S=S_{\tau}$.
Hence, $\left|C\cap S\right|\leq b_{\tau-1}=\mathcal{O}\left(\log
t\cdot(\log\log t)^{2}\right)$.

For $i=1$,

$\left|C\cap S_{1}\right|\leq\left|C\cap S_{0}\right|=\left|C\cap
V_{t}\right|\leq t\leq b_{0}.$

The first inequality follows as $S_{1}\subseteq S_{0}$; the second equality
follows as $S_{0}=V_{t}$; the third inequality follows from the given
condition that $\left|C\cap V_{t}\right|\leq t$; and the fourth one holds by
the definition of $b_{0}$.

Suppose the statement holds for each $i$ with $1\leq i\leq\ell-1$, that is,
$\left|C\cap S_{i}\right|\leq b_{i-1}$ for each $i$ with $1\leq i\leq\ell-1$.
Now we argue for $i=\ell$. If $\left|C\cap S_{\ell-1}\right|\leq b_{\ell-1}$,
then $\left|C\cap S_{\ell}\right|\leq b_{\ell-1}$, as $S_{\ell}\subseteq
S_{\ell-1}$. So, let us assume that $\left|C\cap
S_{\ell-1}\right|>b_{\ell-1}$.

Consider the $\ell$-th iteration of Uniform-Center: it calls algorithm
$\mbox{{\sc Sample-And-Solve}}(S_{\ell-1},p_{\ell-1},r)$, and produces
$S_{\ell}$ as the set of intermediate centers. Let $H_{\ell}\subseteq
S_{\ell-1}$ be the set of hubs sampled in the call of $\mbox{{\sc Sample-And-
Solve}}(S_{\ell-1},p_{\ell-1},r)$, where each point in $S_{\ell-1}$
(independently) included in $H_{\ell}$ with probability $p_{\ell-1}$.

Before proceeding, we make two observations:

######  Observation 5.4.

The probability, that at least one point from $C\cap S_{\ell-1}$ is in
$H_{\ell}$, is at least $1-\frac{1}{t^{\Omega(1)}}.$

###### Proof.

The probability, that no point in $C\cap S_{\ell-1}$ ($\left|C\cap
S_{\ell-1}\right|>b_{\ell-1}$) is included in $H_{\ell}$, is at most

$\left(1-p_{\ell-1}\right)^{b_{\ell-1}}=\left(1-\frac{1}{s_{\ell-1}}\right)^{b_{\ell-1}}\leq\frac{1}{t^{\Omega(1)}}.$

Here, we have used that $b_{\ell-1}=(1+\eta)^{\ell-1}s_{\ell-1}\log
t\cdot(\log\log t)^{2}$. ∎

######  Observation 5.5.

With probability at least $1-\frac{1}{t^{\Omega(1)}}$, the number of points in
$C\cap S_{\ell-1}$ that are in $H_{\ell}$ is at most $b_{\ell-1}$.

###### Proof.

By induction hypothesis, $\left|C\cap S_{\ell-1}\right|\leq b_{\ell-2}$. The
expected number of points of $C\cap S_{\ell-1}$ that are in $H_{\ell}$ is

$\displaystyle{\left|C\cap S_{\ell-1}\right|}\cdot\frac{1}{s_{\ell-1}}$
$\displaystyle\leq$ $\displaystyle\frac{b_{\ell-2}}{s_{\ell-1}}$
$\displaystyle=$ $\displaystyle\frac{(1+\eta)^{\ell-2}s_{\ell-2}\log
t\cdot(\log\log t)^{2}}{s_{\ell-1}}$ $\displaystyle=$
$\displaystyle(1+\eta)^{\ell-2}s_{\ell-1}\log t\cdot(\log\log t)^{2}=\mu.$

By using Chernoff bound (A.1), the probability, that the number of points of
$C\cap S_{\ell-1}$ that are in $H_{\ell}$ is more than
$(1+\eta)\mu=b_{\ell-1}$, is at most
$e^{-\frac{\eta^{2}\mu}{3}}\leq\frac{1}{t^{\Omega(1)}}.$ ∎

Observations 5.4 and 5.5, along with 4.4, give us that $\left|C\cap
S_{\ell}\right|=\left|H_{\ell}\right|\leq b_{\ell-1}$ with probability at
least $1-\frac{1}{t^{\Omega(1)}}$. ∎

##  6 The main algorithm

In this section, we present our main algorithm Ext-$k$-Center. Recall the
overall description of Ext-$k$-Center in Section 2. Ext-$k$-Center has two
phases. In Phase 1, it calls Uniform-Center $\alpha$ times, and in Phase 2, it
calls Sample-And-Solve $\beta$ times, where $\alpha$ is the input precision
parameter and $\beta=\Theta(\log^{(\alpha+1)}n)$. The formal algorithm is
described in Algorithm 5. We prove the round complexity and space complexity
of Ext-$k$-Center in 6.1, the approximation guarantee in 6.2 and the bound on
the number of centers in 6.3.

Input: Set $P$ of $n$ points; tradeoff parameter $\alpha$; radius parameter
$r\in\mathbb{R}^{+}$.

Output: A set $T\subseteq P$ of centers.

1 begin

2

3 Phase 1:

4 $T_{0}\leftarrow P$, $t_{0}=n$, and $r_{0}=\log\log n$.

5 for  _$(j=1~{}\mbox{to}~{}\alpha)$_ do

6 Phase 1.j:

7 $T_{j}\leftarrow\mbox{{\sc Uniform}-{\sc Center}}(T_{j-1},r_{j-1},t_{j-1})$.

8 $t_{j}=\Theta(\log t_{j-1}\cdot(\log\log t_{j-1})^{d+2})$.

9 // Note that $t_{j}=\widetilde{\Theta}(\log
t_{j-1})=\widetilde{\Theta}(\log^{(j)}n).$

10 $r_{j}=\frac{r}{\log\log t_{j}}.$

11 end for

12 Phase 2:

13 for  _ $(i=1~{}\mbox{to}~{}\beta=\Theta(\log^{(\alpha+1)}n))$_ do

14

15 Phase 2.i:

16 $T_{\alpha+i}\leftarrow\mbox{{\sc Sample-And-
Solve}}(T_{\alpha+i-1},\frac{1}{2},r)$.

17 end for

18

19 Report $T=T_{\alpha+\beta}$.

20 end

21

Algorithm 5 Ext-$k$-Center ($P,r$)

######  Lemma 6.1 (Round complexity and global space of Ext-$k$-Center).

Consider Ext-$k$-Center ($P,t$), as described in Algorithm 5. The number of
rounds taken by the algorithm is $\mathcal{O}(\log\log n)$ and the global
space used by the algorithm is
${\mathrm{g}}=\widetilde{\mathcal{O}}\left(n^{1+\rho}\cdot\log\Delta\right)$.

###### Proof.

For any $j$ with $1\leq j\leq\alpha$, in Phase 1.j, Ext-$k$-Center ($P,r$)
calls $\mbox{{\sc Uniform}-{\sc Center}}(T_{j-1},r_{j-1},t_{j-1})$. By Lemma
5.1 (i), the total number of rounds spent by Ext-$k$-Center ($P,r$) in Phase 1
is $\sum_{j=1}^{\alpha}\mathcal{O}\left(\log\log
t_{j-1}\right)=\mathcal{O}\left(\log\log n\right)$. This is because $t_{0}=n$,
$t_{j}=\widetilde{\Theta}\left(\log t_{j-1}\right)$ for any $j\geq 1$, that
is, $t_{j}=\widetilde{\Theta}\left(\log^{(j)}n\right)$. In Phase 2,
Ext-$k$-Center ($P,r$) calls Sample-And-Solve for
$\beta=\Theta\left(\log^{(\alpha+1)}n\right)$ times. By 4.1 (ii), the total
number of rounds spent by Ext-$k$-Center ($P,r$) in Phase 2 is
$\mathcal{O}(\beta)=\mathcal{O}\left(\log^{(\alpha+1)}n\right)$. So, the round
complexity of Ext-$k$-Center follows. The global space complexity of
Ext-$k$-Center follows from the global space complexities of Uniform-Center
and Sample-And-Solve (see Lemma 5.1 and 4.1(ii), respectively). ∎

######  Lemma 6.2 (Approximation guarantee of Ext-$k$-Center).

Let us consider Ext-$k$-Center ($P,r$) as described in Algorithm 5. It
produces output $T\subseteq P$ such that $\mbox{{\sc
Cost}}(P,T)=\mathcal{O}(r\cdot(\alpha+\log^{(\alpha+1)}n)).$

###### Proof.

Observe that

$\displaystyle\textsc{cost}(P,T)$
$\displaystyle=\textsc{cost}(T_{0},T_{\alpha+\beta})\leq\textsc{cost}(T_{0},T_{\alpha})+\textsc{cost}(T_{\alpha},T_{\alpha+\beta})\enspace.$

It therefore suffices to show that $\textsc{cost}(T_{0},T_{\alpha})$ and
$\textsc{cost}(T_{\alpha},T_{\alpha+\beta})$ are bounded by
$\mathcal{O}(r\alpha)$ and $\mathcal{O}(r\cdot\log^{(\alpha+1)}n)$,
respectively.

For any $j$ with $1\leq j\leq\alpha$, note that Ext-$k$-Center ($P,r$) calls
$\mbox{{\sc Uniform}-{\sc Center}}(T_{j-1},r_{j-1},t_{j-1})$ in Phase 1.j and
produces $T_{j}$ as the output. So, by 5.2,
$\textsc{cost}(T_{j-1},T_{j})=\mathcal{O}(r_{j-1}\cdot\log\log t_{j-1})$,
which is $\mathcal{O}(r)$. Hence,

$\displaystyle\textsc{cost}(T_{0},T_{\alpha})$
$\displaystyle\leq\sum_{j=1}^{\alpha}\textsc{cost}\left(T_{j-1},T_{j}\right)=\alpha\cdot\mathcal{O}(r)=\mathcal{O}\left(r\cdot\alpha\right)\enspace.$

For any $i$ with $1\leq i\leq\beta$, note that Ext-$k$-Center ($P,r$) calls
$\mbox{{\sc Sample-And-Solve}}(T_{\alpha+i-1},1/2,r)$ in Phase 2.i and
produces $T_{\alpha+i}$ as the output. So, by 4.1 (i),
$\textsc{cost}(T_{\alpha+i-1},T_{\alpha+i})=\mathcal{O}(r).$ Hence, as
$\beta=\Theta(\log^{(\alpha+1)}n)$,

$\displaystyle\textsc{cost}\left(T_{\alpha},T_{\alpha+\beta}\right)$
$\displaystyle\leq\sum\limits_{i=1}^{\beta}\textsc{cost}\left(T_{\alpha+i-1},T_{\alpha+i}\right)=\mathcal{O}(r\cdot\log^{(\alpha+1)}n)\enspace.\qed$

######  Lemma 6.3 (Number of centers reported by Ext-$k$-Center).

Consider Ext-$k$-Center $(P,r)$ as described in Algorithm 5. It produces
output $T$ such that, with probability at least
$1-\frac{1}{(\log^{(\alpha-1)}n)^{\Omega(1)}}$,

$\displaystyle\left|T\right|$
$\displaystyle\leq\left|\mathcal{C}_{r}\right|\left(1+\frac{1}{\widetilde{\Theta}(\log^{(\alpha)}n)}\right)+\widetilde{\Theta}((\log^{(\alpha)}n)^{3})\enspace.$

Here, $\mathcal{C}_{r}$ is a clustering of $P$ that has the minimum number of
centers among all possible clustering of $P$ with cost at most $r$ such that
$\left|\mathcal{C}_{r}\right|=\Omega((\log n)^{c})$, where $c$ is a suitable
constant.

Now, we introduce the notion of _active_ and _inactive_ clusters in the
following definition, which is useful in proving 6.3. Inactive clusters are
clusters which, at some point during Phase 1, fail to reduce in size
sufficiently. After the sub-phase during which they fail to reduce in size
sufficiently, we assume that they never reduce in size again (since this is
the worst case). We are then able to bound the total number of centers in
inactive clusters (6.6). Active clusters, by contrast, always reduce in size
as we expect: the number of centers in active clusters is therefore easy to
bound.

######  Definition 6.4.

Let $\mathcal{C}_{r}$ be an optimal clustering with cost at most $r$. For each
$C\in\mathcal{C}_{r}$ and $j$ with $1\leq j\leq\alpha$, we say $C$ is
_inactive_ in Phase 1.j if $\left|C\cap T_{i}\right|>t_{i}$ for some $i$ with
$1\leq i<j$. Otherwise, if $\left|C\cap T_{i}\right|\leq t_{i}$ for every $i$
with $1\leq i<j$, $C$ is called _active_ in Phase 1.j.

Let $\mathcal{C}_{r}^{\prime}\subseteq\mathcal{C}_{r}$ be the set of clusters
that are active after Phase 1, that is, Phase 1.$\alpha$. By the definition of
active clusters, for each $C\in\mathcal{C}_{r}^{\prime}$, $\left|C\cap
T_{\alpha}\right|\leq t_{\alpha}$. Note that Ext-$k$-Center goes over $\beta$
sub-phases in Phase 2. After Phase 1 and before the start of Phase 2, it has
$T_{\alpha}$ as the set of intermediate centers. For $1\leq i\leq\beta$, in
Phase 2.i, we call $\mbox{{\sc Sample-And-
Solve}}\left(T_{\alpha+i-1},\frac{1}{2},r\right)$, and get $T_{\alpha+i}$ as
the intermediate centers. For $0\leq i\leq\beta$; a cluster
$C\in\mathcal{C}_{r}^{\prime}$ is said to be $i$-_large_ if $\left|C\cap
T_{\alpha+i}\right|\geq 2$. Let $\Gamma_{i}\subseteq\mathcal{C}_{r}^{\prime}$
denote the set of $i$-_large_ clusters, and let $Y_{i}$ denote the total
number of points that are in $i$-large clusters, that is,
$Y_{i}=\sum\limits_{C\in\Gamma_{i}}\left|C\cap T_{\alpha+i}\right|$.

Note that, in 6.3, we want to bound the number of centers in
$T=T_{\alpha+\beta}$. We first observe that $\left|T\right|$ can be expressed
as the sum of three quantities:

######  Observation 6.5.

$\left|T\right|=\left|T_{\alpha+\beta}\right|=\left|\mathcal{C}_{r}\right|+Y_{\beta}+\sum\limits_{C\in\mathcal{C}_{r}\setminus\mathcal{C}_{r}^{\prime}}\left|C\cap
T_{\alpha}\right|$.

###### Proof.

Observe that since $T_{\alpha+\beta}\subseteq T_{\alpha}$, we obtain,

$\displaystyle T_{\alpha+\beta}$
$\displaystyle=\sum_{C\in\mathcal{C}_{r}\setminus\mathcal{C}_{r}^{\prime}}\left|C\cap
T_{\alpha+\beta}\right|+\sum_{C\in\mathcal{C}_{r}^{\prime}}\left|C\cap
T_{\alpha+\beta}\right|$
$\displaystyle\leq\sum_{C\in\mathcal{C}_{r}\setminus\mathcal{C}_{r}^{\prime}}\left|C\cap
T_{\alpha}\right|+\sum_{C\in\mathcal{C}_{r}^{\prime}}\left|C\cap
T_{\alpha+\beta}\right|\enspace.$

To bound the second inequality by $\left|\mathcal{C}_{r}\right|+Y_{\beta}$,
observe that

$\displaystyle\sum_{C\in\mathcal{C}_{r}^{\prime}}\left|C\cap
T_{\alpha+\beta}\right|$
$\displaystyle=\\!\\!\\!\sum_{C\in\mathcal{C}_{r}^{\prime}:\left|C\cap
T_{\alpha+\beta}\right|=1}\\!\\!\\!\left|C\cap
T_{\alpha+\beta}\right|+\\!\\!\\!\\!\\!\\!\sum_{C\in\mathcal{C}_{r}^{\prime}:\left|C\cap
T_{\alpha+\beta}\right|\geq 2}\\!\\!\\!\left|C\cap T_{\alpha+\beta}\right|$
$\displaystyle\leq\left|\mathcal{C}_{r}^{\prime}\right|+Y_{\beta}\leq\left|\mathcal{C}_{r}\right|+Y_{\beta}\enspace,$

which used that $\mathcal{C}_{r}^{\prime}\subseteq\mathcal{C}_{r}$. This
yields 6.5. ∎

In the following lemmas, we bound
$\sum_{C\in\mathcal{C}_{r}\setminus\mathcal{C}_{r}^{\prime}}\left|C\cap
T_{\alpha}\right|$ and $Y_{\beta}$, and (with 6.5) the result of 6.3
immediately follows from these bounds. Lemmas 6.6 and 6.7 are technical that
we will prove later.

######  Lemma 6.6.

With probability at least
$1-\sum_{i=1}^{\alpha}\frac{1}{t_{i-1}^{\Omega(1)}}$,
$\sum_{C\in\mathcal{C}_{r}\setminus\mathcal{C}_{r}^{\prime}}\left|C\cap
T_{\alpha}\right|$ is
$\mathcal{O}\left(\frac{\left|\mathcal{C}_{r}\right|}{(\log^{(\alpha)}n)^{\Omega(1)}}\right)$,
that is, the number of points in $T_{\alpha}$ that are present in clusters
that are inactive after Phase 1 is
$\mathcal{O}\left(\frac{\left|\mathcal{C}_{r}\right|}{(\log^{(\alpha)}n)^{\Omega(1)}}\right)$.

######  Lemma 6.7.

With probability at least $1-\frac{1}{t_{\alpha-1}^{\Omega(1)}}$, we have
$Y_{\beta}=\mathcal{O}\left(\frac{\left|\mathcal{C}_{r}\right|}{t_{\alpha}}+t_{\alpha}^{3}\cdot\log
t_{\alpha}\right)$.

###### Proof of 6.3 using 6.6 and 6.7.

From the above two lemmas along with 6.5 and the fact
$t_{j}=\widetilde{\Theta}(\log^{(j)}n)$, we have the following bound on
$\left|T\right|$ with probability at least
$1-\sum\limits_{i=1}^{\alpha}\frac{1}{t_{i-1}^{\Omega(1)}}\geq
1-\frac{1}{(\log^{(\alpha-1)}n)^{\Omega(1)}}$:

$\displaystyle\left|T\right|\leq\left|\mathcal{C}_{r}\right|\left(1+\frac{1}{\widetilde{\Theta}(\log^{(\alpha)}n)}\right)+\widetilde{\Theta}\left((\log^{(\alpha)}n)^{3}\right)\enspace.$

Hence, we are done with the proof of 6.3. ∎

### Proof of 6.6

We prove 6.6 by using the following lemma, which we prove later.

######  Lemma 6.8.

Consider Ext-$k$-Center ($P,r$) as described in Algorithm 5 and Phase 1. With
probability at least $1-\sum_{i=1}^{\alpha}\frac{1}{t_{i-1}^{\Omega(1)}}$, the
following holds: the number of clusters $C\in\mathcal{C}_{r}$, such that $C$
is active in Phase 1.i but inactive after Phase 1.i, is at most
$\mathcal{O}\left(\frac{\left|\mathcal{C}_{r}\right|}{t_{i-1}^{\Omega(1)}}\right)$,
where $1\leq i\leq\alpha$.

###### Proof of 6.6 using 6.8.

Let us partition the clusters in $\mathcal{C}_{r}^{\prime}$ into
$\mathcal{A}_{1},\ldots,\mathcal{A}_{\alpha}$, where $\mathcal{A}_{i}$ is the
set of clusters that are active in Phase 1.i but inactive after Phase 1.i,
where $1\leq i\leq\alpha$. Consider a cluster $C\in\mathcal{A}_{i}$. By the
definition of $\mathcal{A}_{i}$, $\left|C\cap T_{i-1}\right|\leq t_{i-1}$.
That is, for each $C\in\mathcal{A}_{i}$, $\left|C\cap T_{\alpha}\right|\leq
t_{i-1}$, because $T_{0}\supseteq T_{1}\supseteq\ldots\supseteq T_{\alpha}$.

Applying 6.8 , we have
$\left|\mathcal{A}_{i}\right|={\color[rgb]{0,0,0}\mathcal{O}\left(\frac{\left|\mathcal{C}_{r}\right|}{t_{i-1}^{\Omega(1)}}\right)}$
for each $i~{}(1\leq i\leq\alpha)$, with probability at least
$1-\sum_{i=1}^{\alpha}\frac{1}{t_{i-1}^{\Omega(1)}}$. Hence, with the same
probability,

$\displaystyle\sum_{C\in\mathcal{C}_{r}\setminus\mathcal{C}_{r}^{\prime}}\left|C\cap
T_{\alpha}\right|$
$\displaystyle\leq\sum_{i=1}^{\alpha}\sum_{C\in\mathcal{A}_{i}}\left|T_{\alpha}\cap
C\right|=\sum_{i=1}^{\alpha}\left|\mathcal{A}_{i}\right|t_{i-1}$
$\displaystyle=\mathcal{O}\left(\sum_{i=1}^{\alpha}\frac{\left|\mathcal{C}_{r}\right|}{t_{i-1}^{\Omega(1)}}\right)=\mathcal{O}\left(\frac{\left|\mathcal{C}_{r}\right|}{\left(\log^{(\alpha)}n\right)^{\Omega(1)}}\right)\enspace.$

The last step uses that $t_{i}=\widetilde{\Theta}\left(\log^{(i)}n\right)$. ∎

###### Proof of 6.8.

Consider $i$ with $1\leq i\leq\alpha$. Let $\mathcal{A}_{i}$ be the set of
clusters that were active in Phase 1.i but inactive after Phase 1.i, and let
$\mathcal{B}_{i}\supseteq\mathcal{A}_{i}$ be the set of clusters that were
active in Phase 1.i. It suffices to show that
$\left|\mathcal{A}_{i}\right|=\mathcal{O}\left(\frac{\left|\mathcal{C}_{r}\right|}{t_{i-1}^{\Omega(1)}}\right)$
holds with probability at least $1-\frac{1}{t_{i-1}^{\Omega(1)}}$.

For $C\in\mathcal{B}_{i}$, let $X_{C}$ be the random variable defined as

$\displaystyle X_{C}$ $\displaystyle=\begin{cases}1&\text{ if }\left|C\cap
T_{i}\right|>t_{i}\\\ 0&\mbox{otherwise.}\end{cases}$

Observe that $\left|\mathcal{A}_{i}\right|=\sum_{C\in\mathcal{B}_{i}}X_{C}$.

######  Claim 6.9.

The probability that $X_{C}=1$ is
$\mathcal{O}\left(\frac{1}{t_{i-1}^{\Omega(1)}}\right).$

Using the above claim, we prove 6.8 separately for $i=1$ and $i\geq 1$.

For $i=1$, applying the union bound over all
$C\in\mathcal{B}_{i}=\mathcal{B}_{1}$, the probability that there exists a
$C\in\mathcal{B}_{1}$ such that $X_{C}=1$ is at most
$\frac{\left|\mathcal{B}_{1}\right|}{t_{0}^{\Omega(1)}}<\frac{1}{t_{0}^{\Omega(1)}}$.
It is because $\left|\mathcal{B}_{1}\right|\leq n$ and $t_{0}=n$. This implies
that $\left|\mathcal{A}_{1}\right|=0$ with probability at least
$1-\frac{1}{t_{0}^{\Omega(1)}}$. Note that we are done for the case $i=1.$

For $2\leq i\leq\alpha$,
$\mathbb{E}[\left|\mathcal{A}_{i}\right|]=\mathcal{O}\left(\frac{\left|\mathcal{B}_{i}\right|}{t_{i-1}^{\Omega(1)}}\right)=\mathcal{O}\left(\frac{\left|\mathcal{C}_{r}\right|}{t_{i-1}^{\Omega(1)}}\right)$.
As $i\geq 2$, $t_{i-1}\leq t_{1}=\widetilde{\mathcal{O}}(\log n)$. Recall
that, we consider $\left|\mathcal{C}_{r}\right|=\Omega((\log n)^{c})$ for a
suitable constant $c$. So, we can assume that
$\frac{\left|\mathcal{C}_{r}\right|}{t_{i-1}^{\Omega(1)}}\geq\log t_{i-1}$.
Using a Chernoff bound (A.1), $\Pr\left(\left|\mathcal{A}_{i}\right|\geq
c_{1}\cdot\frac{\left|\mathcal{C}_{r}\right|}{t_{i-1}^{\Omega(1)}}\right)\leq\frac{1}{t_{i-1}^{\Omega(1)}},$
where $c_{1}$ is a suitable large constant. So, we are done with the proof of
6.8, except for the proof of 6.9.

###### Proof of 6.9.

Consider the clustering $\mathcal{C}_{r_{i-1}}^{t_{i-1}}$ of $T_{i-1}$ as
follows. For each $C\in\mathcal{C}_{r}$, consider the partition of cluster $C$
into at most $z=\mathcal{O}\left(\left(\log\log t_{i-1}\right)^{d}\right)$
many clusters $C_{1}.\ldots,C_{z}$ such that the radius of each $C_{i}$ is at
most $r_{i-1}$. For each $C_{i}$ ($i\in[z]$), the corresponding cluster in
$\mathcal{C}_{r_{i-1}}^{t_{i-1}}$ is $C_{i}^{\prime}=C_{i}\cap T_{i-1}$. So,
$\left|\mathcal{C}_{r_{i-1}}^{t_{i-1}}\right|=\left|\mathcal{C}_{r}\right|\cdot\mathcal{O}\left(\left(\log\log
t_{i-1}\right)^{d}\right).$

Consider the particular $C\in\mathcal{B}_{i}$. By 6.4, $\left|C\cap
T_{i-1}\right|\leq t_{i-1}$. If we consider the partition of $C$ into
$C_{1},\ldots,C_{z}$ in $\mathcal{C}_{r_{i-1}}^{t_{i-1}}$, then
$\left|C_{y}\cap T_{i-1}\right|\leq t_{i-1}$ for each $y\in[z]$. Let
$\mathcal{B}_{i}^{\prime}$ be the set of clusters in
$\mathcal{C}_{r_{i-1}}^{t_{i-1}}$ that are formed due to the partition of some
$C\in\mathcal{B}_{i}$. So, for each $C^{\prime}\in\mathcal{B}_{i}^{\prime}$,
we have $\left|C^{\prime}\cap T_{i-1}\right|\leq t_{i-1}.$

Consider Phase 1.i of Ext-$k$-Center: we get $T_{i}$ as the current set of
centers by calling $\mbox{{\sc Uniform}-{\sc
Center}}(T_{i-1},r_{i-1},t_{i-1})$. Let us apply 5.3 with $t=t_{i-1}$,
$V_{t}=T_{i-1}$, $r=r_{i-1}$, $S=T_{i}$, and
$\mathcal{C}_{r}^{t}=\mathcal{C}_{r_{k-1}}^{t_{k-1}}$. For $y\in[z]$, with
probability at least $1-\frac{1}{t_{i-1}^{\Omega(1)}}$, we have
$\left|C_{y}\cap T_{i}\right|=\mathcal{O}\left(\log t_{i-1}\cdot\left(\log\log
t_{i-1}\right)^{2}\right)$. Applying union bound for all $y\in[z]$, with
probability at least $1-\frac{1}{t_{i-1}^{\Omega(1)}}$, we have

$\left|C\cap T_{i}\right|=\sum_{y\in[z]}\left|C_{y}\cap
T_{i}\right|=\mathcal{O}\left(\log t_{i-1}\cdot\left(\log\log
t_{i-1}\right)^{d+2}\right)=t_{i}.$

This is because $z=\mathcal{O}\left((\log\log t_{i-1})^{d+2}\right)$, and we
are done with the proof of the claim. ∎

This completes the proof of 6.6. ∎

### Proof of 6.7

We prove 6.7 by using the following lemma, which we prove later.

######  Lemma 6.10.

Let $\zeta\in(0,1)$ be a suitable constant, let $i$ be such that $1\leq
i\leq\beta$ with $Y_{i-1}=\Omega\left(t_{\alpha}^{3}\log t_{\alpha}\right)$.
With probability $1-\frac{1}{t_{\alpha}^{\Omega(1)}}$,
$Y_{i}\leq\sum_{C\in\Gamma_{i-1}}\left|C\cap T_{\alpha+i}\right|\leq\zeta\cdot
Y_{i-1}.$

Applying the union bound over all $i$’s in $1$ to $\beta$, with probability at
least $1-\frac{1}{t_{\alpha}^{\Omega(1)}}$, we have
$Y_{\beta}=\zeta^{\beta}Y_{0}+t_{\alpha}^{3}\log t_{\alpha}.$ As
$Y_{0}=\mathcal{O}\left(\left|\mathcal{C}_{r}^{\prime}\right|\cdot
t_{\alpha}\right)$ $=\mathcal{O}\left(\left|\mathcal{C}_{r}\right|\cdot
t_{\alpha}\right)$, $\beta=\Theta\left(\log^{(\alpha+1)}n\right)$ and $\zeta$
is chosen suitably, we are done with the proof of 6.7. ∎

###### Proof of 6.10.

As $Y_{i}=\sum_{C\in\Gamma_{i}}\left|C\cap T_{\alpha+i}\right|$ and
$\Gamma_{i}\subseteq\Gamma_{i-1}$,
$Y_{i}\leq\sum_{C\in\Gamma_{i-1}}\left|C\cap T_{\alpha+i}\right|$ follows.

For the other part, $\sum_{C\in\Gamma_{i-1}}\left|C\cap
T_{\alpha+i}\right|\leq\zeta\cdot Y_{i-1}$, let $Z_{C}=\left|C\cap
T_{\alpha+i}\right|$ and $Z=\sum_{C\in\Gamma_{i-1}}Z_{C}$. Now consider the
following claim, which we will prove right after proving 6.10.

######  Claim 6.11.

Let $C\in\Gamma_{i-1}$. The probability that $Z_{C}=\left|C\cap
T_{\alpha+i}\right|\leq\frac{3}{4}\cdot\left|C\cap T_{\alpha+i-1}\right|$ is
at least a constant $\kappa\in(0,1)$.

Note that $T_{\alpha+i}\subseteq T_{\alpha+i-1}$. So, $\left|C\cap
T_{\alpha+i}\right|\leq\left|C\cap T_{\alpha+i-1}\right|$ always. For
$C\in\Gamma_{i-1}$, note that $\left|T_{\alpha+i-1}\right|\leq t_{\alpha}$.
From the above claim

$\displaystyle\mathbb{E}[Z_{C}]$ $\displaystyle=\mathbb{E}[\left|C\cap
T_{\alpha+i}\right|]$ $\displaystyle\leq\kappa\cdot\frac{3}{4}\left|C\cap
T_{\alpha+i-1}\right|+(1-\kappa)\cdot\left|C\cap T_{\alpha+i-1}\right|$
$\displaystyle\leq\zeta^{{}^{\prime}}\left|C\cap
T_{\alpha+i-1}\right|\enspace.$

where $\zeta^{\prime}$ is a suitable constant. Recalling the definition of
$Y_{i-1}$, we have

$\mathbb{E}[Z]\leq\zeta^{{}^{\prime}}\sum_{C\in\Gamma_{i-1}}\left|C\cap
T_{\alpha+i-1}\right|=\zeta^{\prime}Y_{i-1}.$

Moreover, $0\leq Z_{C}\leq t_{\alpha}$ for each $C\in\Gamma_{i-1}$. Hence,
applying a Hoeffding bound (A.2), we have

$\displaystyle\mbox{Pr}\left(Z\geq\zeta Y_{i-1}\right)$
$\displaystyle=\mbox{Pr}\left(Z\geq\mathbb{E}[Z]+\zeta_{1}Y_{i-1}\right)$
$\displaystyle\leq
e^{-\frac{\zeta_{1}^{2}Y_{i-1}^{2}}{\left|\Gamma_{i-1}\right|t_{\alpha}^{2}}}\leq
e^{-\frac{\zeta_{1}^{2}Y_{i-1}^{2}}{\left|\Gamma_{i-1}\right|t_{\alpha}^{2}}}\leq{1}/{t_{\alpha-1}^{\Omega(1)}}\enspace.$

The last inequality folllows from $Y_{i-1}\geq
2\left|\Gamma_{i-1}\right|~{}\mbox{and}~{}Y_{i-1}=\Omega(t_{\alpha}^{3}\cdot\log
t_{\alpha})$. This concludes the proof of 6.10 since we have
$Z=\sum_{C\in\Gamma_{i-1}}\left|C\cap T_{\alpha+i}\right|$. ∎

We are left with only the proof of 6.11.

###### Proof of 6.11.

We prove

  1. (i)

$\mbox{Pr}\left(Z_{C}\leq\frac{3}{4}\left|C\cap
T_{\alpha+i-1}\right|\right)\geq\mbox{Pr}(Z_{C}=1)=\frac{\left|C\cap
T_{\alpha+i-1}\right|}{2^{\left|C\cap T_{\alpha+i-1}\right|}}$;

  2. (ii)

$\mbox{Pr}\left(Z_{C}\leq\frac{3}{4}\left|C\cap
T_{\alpha+i-1}\right|\right)\geq 1-\frac{1}{2^{\Omega(\left|C\cap
T_{\alpha+i-1}\right|)}}$.

From the above two statements, we are done with the claim by setting
$\kappa=\max\left\\{\frac{\left|C\cap T_{\alpha+i-1}\right|}{2^{\left|C\cap
T_{\alpha+i-1}\right|}},1-e^{-\Omega(\left|C\cap
T_{\alpha+i-1}\right|)}\right\\}$, which is $\Omega(1)$.

Note that Ext-$k$-Center calls $\mbox{{\sc Sample-And-
Solve}}\left(T_{\alpha+i-1},\frac{1}{2},r\right)$ in Phase 2.i. In $\mbox{{\sc
Sample-And-Solve}}\left(T_{\alpha+i-1},\frac{1}{2},r\right)$, let
$H_{i}\subseteq T_{\alpha+i-1}$ be the set of hubs sampled, where each point
in $T_{\alpha+i-1}$ is (independently) included in $H_{i}$ with probability
$\frac{1}{2}$.

For (i), $\mbox{Pr}\left(Z_{C}\leq\frac{3}{4}\left|C\cap
T_{\alpha+i-1}\right|\right)\geq\mbox{Pr}(Z_{C}=1)$ is direct as $\left|C\cap
T_{\alpha+i-1}\right|\geq 2$. From 4.4, $Z_{C}=\left|C\cap
T_{\alpha+i}\right|=1$ if $\left|H_{i}\right|=1$. So,

$\displaystyle\mbox{Pr}(Z_{C}=1)$ $\displaystyle=\frac{\left|C\cap
T_{\alpha+i-1}\right|}{2^{\left|C\cap T_{\alpha+i-1}\right|}}\enspace.$

Now, we will prove (ii). From 4.4, $Z_{C}=\left|C\cap
T_{\alpha+i}\right|=\left|H_{i}\right|$ if $\left|H_{i}\right|>0$. Observe
that $\mbox{Pr}(H_{i}>0)=1-\frac{1}{2^{\left|C\cap T_{\alpha+i-1}\right|}}$.
The expected number of points in $H_{i}$ is $\frac{\left|C\cap
T_{\alpha+i-1}\right|}{2}$. Using Chernoff bound (A.1),
$\mbox{Pr}\left(\left|H_{i}\right|>\frac{3}{4}\left|C\cap
T_{\alpha+i-1}\right|\right)\leq e^{-\Omega\left(\left|C\cap
T_{\alpha+i-1}\right|\right)}.$ Hence, putting things together,

$\displaystyle\mbox{Pr}\left(Z_{C}\leq\frac{3}{4}\left|C\cap
T_{\alpha+i-1}\right|\right)$
$\displaystyle\geq\mbox{Pr}(\left|H_{i}\right|>0)\cdot\mbox{Pr}\left(\left|H_{i}\right|\leq\frac{3}{4}\left|C\cap
T_{\alpha+i-1}\right|\right)$
$\displaystyle\geq\left(1-\frac{1}{2^{\left|C\cap
T_{\alpha+i-1}\right|}}\right)\cdot\left(1-\frac{1}{e^{\Omega\left(\left|C\cap
T_{\alpha+i-1}\right|\right)}}\right)$ $\displaystyle\geq
1-\frac{1}{2^{\Omega(\left|C\cap T_{\alpha+i-1}\right|)}}\enspace.$

∎

##  7 Conclusions

In this paper we show that even for large values of $k$, the classic
$k$-center clustering problem in low-dimensional Euclidean space can be
efficiently and very well approximated in the parallel setting of low-local-
space MPC. While some earlier works (see, e.g., [EIM11, MKC+15, CPP19]) were
able to obtain constant-round MPC algorithms, they were relying on a large
local space ${\mathrm{s}}\gg k$ allowing to successfully apply the core-set
approach, which permits only limited communication. On the other hand, the
low-local-space setting considered in this paper seems to require extensive
communication between the machines to achieve any reasonable approximation
guarantees. Therefore we believe (without any evidence) that the number of
rounds of order $\mathcal{O}(\log\log n)$ may be almost as good as it gets.
Also, we concede that our algorithm does not achieve a constant approximation
guarantee, but we feel the approximation bound of $\mathcal{O}(\log^{*}n)$ is
almost as good. Finally, our algorithm does not resolve the perfect setting of
the $k$-center clustering in that it allows in the solution slightly more
centers, $k+o(k)$ centers. Improving on these three parameters is the main
open problem left by our work.

We believe that solely using the technique in this paper, improving the
approximation factor and/or number of rounds may not be possible (a detailed
explanation is in Appendix C), but the approach may be useful for related
problems in MPC or other models. We remark that the extra space in global
space complexity is mainly due to the use of LSH; note that, even in the RAM
model setting, the use of LSH requires some extra space.

Our work naturally suggests some open directions for future research:

  * •

Can we improve the approximation factor beyond $\mathcal{O}(\log^{*}n)$ and/or
the number of rounds beyond $\mathcal{O}(\log\log n)$?

  * •

In the large $k$ regime, can we design an efficient algorithm that uses
(almost) linear global space?

  * •

In the large $k$ regime, can we design an efficient algorithm that reports
exactly $k$ centers?

  * •

Are similar results possible for the related $k$-means and $k$-medians
problems for large $k$ in MPC?

  * •

What MPC results are possible when the points are in high-dimensional
Euclidean space or in a general metric space? Our work has a limitation to go
beyond constant dimension as we are not aware of any _efficient_ LSH for high
dimension.

## References

  * [ANOY14] Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev.  Parallel algorithms for geometric graph problems.  In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 574–583, 2014.
  * [BEFM21] MohammadHossein Bateni, Hossein Esfandiari, Manuela Fischer, and Vahab Mirrokni.  Extreme $k$-center clustering.  In Proceedings of the 35th AAAI Conference on Artificial Intelligence(AAAI), pages 3941–3949, 2021.
  * [BKS17] Paul Beame, Paraschos Koutris, and Dan Suciu.  Communication steps for parallel query processing.  Journal of the ACM, 64(6):40:1–40:58, 2017.
  * [BT10] Guy E Blelloch and Kanat Tangwongsan.  Parallel approximation algorithms for facility-location problems.  In Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures, pages 315–324, 2010.
  * [CŁM+18] Artur Czumaj, Jakub Ła̧cki, Aleksander Ma̧dry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski.  Round compression for parallel matching algorithms.  In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), pages 471–484, 2018.
  * [CPP19] Matteo Ceccarello, Andrea Pietracaprina, and Geppino Pucci.  Solving $k$-center clustering (with outliers) in MapReduce and streaming, almost as accurately as sequentially.  Proceedings of the VLDB Endowment, 12(7):766–778, 2019.
  * [CSWZ16] Jiecao Chen, He Sun, David P. Woodruff, and Qin Zhang.  Communication-optimal distributed clustering.  In Proceedings of the 29th Annual Conference on Neural Information Processing Systems (NIPS), pages 3720–3728, 2016.
  * [DF85] Martin E. Dyer and Alan M. Frieze.  A simple heuristic for the $p$-centre problem.  Operations Research Letters, 3(6):285–288, 1985.
  * [DG08] Jeffrey Dean and Sanjay Ghemawat.  MapReduce: Simplified data processing on large clusters.  Communications of the ACM, 51(1):107–113, January 2008.
  * [EIM11] Alina Ene, Sungjin Im, and Benjamin Moseley.  Fast clustering using MapReduce.  In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 681–689, 2011.
  * [Gon85] Teofilo F. Gonzalez.  Clustering to minimize the maximum intercluster distance.  Theoretical Computer Science, 38:293–306, 1985.
  * [GSZ11] Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang.  Sorting, searching, and simulation in the MapReduce framework.  In Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC), pages 374–383, 2011.
  * [HIM12] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani.  Approximate nearest neighbor: Towards removing the curse of dimensionality.  Theoretical Computer Science, 8(1):321–350, 2012.
  * [HN79] Wen-Lian Hsu and George L. Nemhauser.  Easy and hard bottleneck location problems.  Discrete Applied Mathematics, 1(3):209–215, 1979.
  * [HS85] Dorit S. Hochbaum and David B. Shmoys.  A best possible heuristic for the $k$-center problem.  Mathematics of Operations Research, 10(2):180–184, 1985.
  * [IBY+07] Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly.  Dryad: Distributed data-parallel programs from sequential building blocks.  SIGOPS Operating Systems Review, 41(3):59–72, March 2007.
  * [KSV10] Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii.  A model of computation for MapReduce.  In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938–948, 2010.
  * [MKC+15] Gustavo Malkomes, Matt J. Kusner, Wenlin Chen, Kilian Q. Weinberger, and Benjamin Moseley.  Fast distributed $k$-center clustering with outliers on massive data.  In Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS), pages 1063–1071, 2015.
  * [Whi15] Tom White.  Hadoop: The Definitive Guide: Storage and Analysis at Internet Scale.  O’Reilly Media, Sebastopol, CA, 4th edition, 2015.
  * [WLF+09] Haofen Wang, Yan Liang, Linyun Fu, Gui-Rong Xue, and Yong Yu.  Efficient query expansion for advertisement search.  In Proceedings of the 32nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), pages 51–58, 2009.
  * [XW05] Rui Xu and Donald Wunsch.  Survey of clustering algorithms.  IEEE Transactions on Neural Networks, 16(3):645–678, 2005.
  * [ZCF+10] Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica.  Spark: Cluster computing with working sets.  In Proceedings of the 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud), 2010.

## Appendix

##  Appendix A Concentration inequalities

In our analysis we use some basic and standard concentration inequalities,
which we present here for the sake of completeness.

######  Lemma A.1 (Chernoff bound).

Let $X_{1},\dots,X_{n}$ be independent random variables such that
$X_{i}\in[0,1]$. For $X=\sum_{i=1}^{n}X_{i}$ and
$\mu_{l}\leq\mathbb{E}[X]\leq\mu_{h}$, the following hold for any
$\varepsilon>0$.

$\displaystyle\mbox{Pr}\left(X\geq(1+\varepsilon)\mu_{h}\right)$
$\displaystyle\leq e^{-\mu_{h}\varepsilon^{2}/3}\enspace.$

######  Lemma A.2 (Hoeffding bound).

Let $X_{1},\dots,X_{n}$ be independent random variables such that $a_{i}\leq
X_{i}\leq b_{i}$ and $X=\sum_{i=1}^{n}X_{i}$. Then, for all $\varepsilon>0$,

$\displaystyle\mbox{Pr}\left(\left|X-\mathbb{E}[X]\right|\geq\varepsilon\right)$
$\displaystyle\leq
2\exp\left({-2\varepsilon^{2}}/{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right)\enspace.$

##  Appendix B Proof of Theorem 1.5

In this section we prove 1.5 using 2.1.

Let us consider algorithm $\mbox{{\sc Ext}-$k$-{\sc Center}}^{\prime}$ that
runs $\psi$ instances, $\psi=\mathcal{O}(\log(\max\\{n,\log\Delta\\}))$, of
the algorithm Ext-$k$-Center in parallel. Let $T(1),\ldots,T(\psi)$ be the
outputs of the runs of Ext-$k$-Center. $\mbox{{\sc Ext}-$k$-{\sc
Center}}^{\prime}$ reports $T^{\prime}=T(i)$ with the minimum cardinality as
the output. Therefore by 2.1, with probability at least
$1-\frac{1}{(\max\\{n,\log\Delta\\})^{\Omega(1)}}$, the following is true for
$\mbox{{\sc Ext}-$k$-{\sc Center}}^{\prime}$:

  1. (i)

the number of rounds spent by $\mbox{{\sc Ext}-$k$-{\sc Center}}^{\prime}$ is
$\mathcal{O}(\log\log n)$ and the global space used by $\mbox{{\sc
Ext}-$k$-{\sc Center}}^{\prime}$ is
$\widetilde{\mathcal{O}}(n^{1+\rho}\log\Delta)$;

  2. (ii)

$\textsc{cost}(P,T^{\prime})=\mathcal{O}(r\cdot(\alpha+\log^{(\alpha+1)}n))$;
and

  3. (iii)

$\left|T^{\prime}\right|\leq\left|\mathcal{C}_{r}\right|(1+\frac{1}{\widetilde{\Theta}(\log^{(\alpha)}n)})$
\+ $\widetilde{\Theta}((\log^{(\alpha)}n)^{3})$.

Next, consider the following observation about $\mbox{{\sc Ext}-$k$-{\sc
Center}}^{\prime}$:

######  Observation B.1.

Let opt be the optimal cost to the $k$-center problem for $P$. If one runs
$\mbox{{\sc Ext}-$k$-{\sc Center}}^{\prime}$ with radius parameter $r$ with
$r\geq\textsc{opt}$, then the number of centers reported by $\mbox{{\sc
Ext}-$k$-{\sc Center}}^{\prime}$ is at most
$k\left(1+\frac{1}{\widetilde{\Theta}(\log^{(\alpha)}n)}\right)+\widetilde{\Theta}((\log^{(\alpha)}n)^{3})$,
with probability at least $1-\frac{1}{(\max\\{n,\log\Delta\\})^{\Omega(1)}}$.

B.1 follows from the bound $\left|\mathcal{C}_{r}\right|\leq k$ for
$r\geq\textsc{opt}$.

Now we describe the algorithm algorithm $\mbox{{\sc Ext}-$k$-{\sc
Center}}^{{}^{\prime\prime}}$, which is the algorithm corresponding to 1.5.
$\mbox{{\sc Ext}-$k$-{\sc Center}}^{{}^{\prime\prime}}$ runs
$\phi=\mathcal{O}(\log\Delta)$ instances of $\mbox{{\sc Ext}-$k$-{\sc
Center}}^{\prime}$, with radius parameters
$r(1)=\Delta,r(2)=\frac{\Delta}{2},r(3)=\frac{\Delta}{4},\ldots,r({\phi})=\mathcal{O}(1)$,
in parallel. Let $T^{\prime}(1),\ldots,T^{\prime}(\phi)$ be the corresponding
outputs of the runs of $\mbox{{\sc Ext}-$k$-{\sc Center}}^{\prime}$.
$\mbox{{\sc Ext}-$k$-{\sc Center}}^{{}^{\prime\prime}}$ reports
$T^{\prime\prime}=T^{\prime}(i)$ as the output such that
$\left|T^{\prime}(i)\right|\leq
k(1+\frac{1}{\widetilde{\Theta}(\log^{(\alpha)}n)})+\widetilde{\Theta}((\log^{(\alpha)}n)^{3})$
and $r(i)$ is the minimum. So, the round complexity and space complexity of
1.5 follow from the round and space complexity guarantee of $\mbox{{\sc
Ext}-$k$-{\sc Center}}^{\prime}$, respectively. From the guarantee of
algorithm $\mbox{{\sc Ext}-$k$-{\sc Center}}^{\prime}$ about the set of
centers returned by it, we have
$\textsc{cost}(P,T^{\prime\prime})=r(i)\cdot(\alpha+{(\log^{(\alpha+1)}n)})$,
and $\left|T^{\prime\prime}\right|\leq
k(1+\frac{1}{\widetilde{\Theta}(\log^{(\alpha)}n)})$ \+
$\widetilde{\Theta}((\log^{(\alpha)}n)^{3})$, with probability at least
$1-\frac{1}{(\max\\{n,\log\Delta\\})^{\Omega(1)}}$. From B.1, $r(i)\leq
2\cdot\textsc{opt}$ with probability at least
$1-\frac{1}{(\max\\{n,\log\Delta\\})^{\Omega(1)}}$. This yields the proof of
guarantee on approximation factor and the number of centers of 1.5.

##  Appendix C Limitation of the techniques

Our algorithm is an iterative algorithm that refines the set of centers
starting with the entire point set as the set of centers. As with many
distributed algorithms, the iterative approach usually does not lead to a
constant round algorithm. In particular, roughly speaking, our algorithm first
samples points with inverse polynomial probability and then increases
probability in a square root fashion. So, to go from $n$ centers to $k$ or
even $\mathcal{O}(k)$ centers, one needs $\Omega(\log\log n))$ rounds.
Increasing the probability along a faster schedule is unlikely to allow us to
sufficiently bound the number of centers while increasing the probability
along a slower schedule will increase the running time. Note also that the
cost of the solution gets added over the rounds in our algorithm. The way our
algorithm works, the cost of the solution in the first phase is
$\mathcal{O}(r)$. After that, each optimal cluster has at most
$\widetilde{\mathcal{O}}(\log^{*}n)$ centers. In phase 2, we apply Sample-And-
Solve for $\mathcal{O}(\log^{*}n)$ rounds with $r$ as the radius that leads to
approximation ratio $\mathcal{O}(\log^{*}n)$. One may think to apply Sample-
And-Solve in Phase 2 with a radius parameter less than $r$ in Phase 2. But in
that case, guaranteeing the total number of centers to be $k+o(k)$ seems
unlikely.