#  $k$-Center Clustering in Distributed Models

Leyla Biabani, Eindhoven University of Technology
Ami Paz, LISN — CNRS & Paris-Saclay University

###### Abstract

The $k$-center problem is a central optimization problem with numerous
applications for machine learning, data mining, and communication networks.
Despite extensive study in various scenarios, it surprisingly has not been
thoroughly explored in the traditional distributed setting, where the
communication graph of a network also defines the distance metric.

We initiate the study of the $k$-center problem in a setting where the
underlying metric is the graph’s shortest path metric in three canonical
distributed settings: the local, congest, and clique models. Our results
encompass constant-factor approximation algorithms and lower bounds in these
models, as well as hardness results for the bi-criteria approximation setting.

keywords: $k$-Center clustering; Distributed graph algorithms; Shortest path
metric

##  1 Introduction

###  1.1 Distributed $k$-Center

The $k$-center problem is a key optimization problem, seeks to locate a small
set of points in space (“centers”) that minimize the maximal distance from
them to any other point. The problem was extensively studied in the
centralized setting, where the points are taken from a metric space, with or
without guarantees on the metric. Over the years, there was also some work on
the $k$-center problem in parallel and distributed models, looking to solve
the problem faster using multiple computational units. As in the centralized
setting, the points and metric under consideration in these works are taken
from some metric space, and it is usually assumed that distances are given to
the computational units by an oracle.

A natural setting for the $k$-center problem is that of a network. We consider
a graph representing a communication network in a natural way, and the goal is
to make $k$ of the nodes into centers while minimizing the maximal distance
between these nodes and all others. Here, the metric space is not arbitrary,
but is the _graph metric_ on the graph itself. This is significant, for
example, when determining server placement within a network to minimize the
maximum delay, as seen in scenarios like content distribution over the
Internet.

Two related, yet different problems are the metric _facility location_
problem, where the goal is to minimize the average distance from the servers
(or equivalently, the sum of distances), and the _online $k$-server_ problem,
where the points and servers can move in space.

In this work, we initiate the study of $k$-center in the distributed setting,
where an undirected graph represents both the communication network and the
problem’s metric. We address the problem in the popular distributed models of
local, congest, and clique, and derive upper and lower bounds. While the
problem was studied earlier in some of these distributed models, it is
important to note that all the prior work considered points in an arbitrary
metric space, independent of the communication graph. As far as we know, our
work is the first to consider the natural setting where the input graph
represents both the network used for communication and the metric on which
$k$-center is solved.

###  1.2 Our Results and Techniques

We present upper and lower bounds for the $k$-center problem in different
distributed models. The metric considered is the shortest-path metric, and the
graphs are unweighted unless otherwise specified.

#### The local Model

A simple and natural model for communication networks is the local model [22],
where the network’s nodes communicate by synchronously exchanging messages of
unbounded size. The local computation time is neglected, and the complexity
measure in this case is the number of communication rounds. In this model, any
problem is solvable in $D$ rounds, where $D$ is the diameter of the graph,
i.e., the largest distance between two nodes in it. Hence, our upper bounds
should be read as the minimum of the given value and $D$, and the lower bounds
only apply for graphs with a diameter larger than the lower bound value.

We start Section 3 by giving a relatively simple algorithm that finds a
$(2k+\epsilon)$-approximate solution to the $k$-center problem in
$O(k/\epsilon)$ rounds of the local model. This result relies on the
assumption that the nodes have unique IDs in ${1,\ldots,n}$ — if we assumed
the range to be larger, even ensuring a specific number of centers would
require global communication. We then show that reducing the approximation
ratio to be below $k-1$ requires $\Omega(n)$ time. We stress that $D\leq n$,
so in $\Omega(n)$ time the nodes can aggregate the full structure of the
network and find an exact solution.

Put differently, our results present two extremes. On the one hand, if a large
approximation ratio of at least $2k+\epsilon$ is allowed, the problem is
simple—for $\epsilon,k$ constants, it is solvable in constant time. On the
other hand, if a lower approximation ratio is required, e.g., a constant that
does not depend on $k$, then the running time is so large that the nodes may
as well compute an optimal solution.

#### The congest Model

The congest model is a restrictive variant of the local model, where the
messages are limited to $O(\log n)$ bits. Specifically, problems are no longer
trivially solvable in $O(D)$ time, and getting a constant approximation is
solvable in non-trivial time, but is challenging.

In Section 4 we present a $2$-approximation congest algorithm for the
$k$-center problem running in $O(kD)$ rounds. It constructs different BFS
trees, sometimes from multiple sources simultaneously, and simulates a
centralized greedy approximation algorithm for the $k$-center problem. On the
other hand, in Section 5 we prove that improving the approximation ratio to
below $4/3$, and hence also finding an exact solution, requires a much longer
time: any algorithm for this problem, even randomized, must take
$\tilde{\Omega}(n/k)$ rounds, and this is true even for graphs of diameter as
small as 12.

This lower-bound proof is rather involved: it uses a reduction to
communication complexity with a twist. Proving congest lower bounds by
reducing them to communication complexity is common in the literature [1, 10,
28], where usually the solution for the congest problem directly implies an
answer communication complexity problem. In our reduction, a new post-
processing phase is added, where the players must do extra computation and
also communicate more after getting the solution to the (approximate)
$k$-center problem and before finding an answer to the communication problem.

#### The clique Model

Finally, in Section 6 we consider the more recent congested clique model,
denoted clique. It resembles the congest, but with an all-to-all
communication—the communication graph is a clique, and the input graph is a
subgraph of it on the same set of nodes. One might think that the
$O(kD)$-round congest algorithm will directly translate to an $O(k)$-round
clique algorithm, as the communication network has a diameter $1$. However,
this it not the case: the congest algorithm builds BFS trees in $O(D)$ time,
and this step cannot be translated to an $O(1)$-round subroutine in the clique
model.

At a high level, we show that finding a $2$-approximate solution for the
$k$-center problem in this model can be done deterministically in the same
time as computing all-pairs-shortest paths, which is $O(n^{1/3})$ for weighted
graphs, and $O(n^{0.158})$ for unweighted graphs [5]. Interestingly, if
$\omega$, the exponent of the (centralized) matrix multiplication problem,
will be discovered to be $2$, the time for distributed matrix multiplication
algorithms $2$-approximation of $k$-center will also be improved, to
$O(n^{\epsilon^{\prime}})$ for any $\epsilon^{\prime}>0$, or even to be poly-
logarithmic. Previous work implies that a $(2+\epsilon)$-approximate solution
for $k$-center can be found in only $O(\operatorname{poly}\log n)$ rounds,
even in weighted graphs [2]. By allowing higher approximation ratios we can
get even faster algorithms, such as a $(4+\epsilon)$-approximation in
$O(\operatorname{poly}\log\log n+k)$ rounds, and up to an $O(\log
n)$-approximation in $O(k)$ rounds.

En route, we prove a new result regarding approximate $k$-center. A simple
greedy algorithm [15] finds a $2$-approximation of $k$-center, assuming the
distance between every two nodes is known. We extend this claim in Lemma 4, to
show that if only a one-way, multiplicative $\alpha$-approximation of the
distances is known, then a similar greedy algorithm gives a
$(2\alpha)$-approximate solution to the $k$-center problem. Hence, by studying
distributed $k$-center, we also provide new insights to the centralized case,
which could be of independent interest.

Unfortunately, current techniques cannot establish lower bounds in the clique
model. Any non-trivial lower bound in this model will imply circuit complexity
lower bounds, solving a long-standing and notoriously hard open problem [13].

##  2 Preliminaries

###  2.1 The $k$-Center Problem

Consider a graph $G=(V,E)$ with nodes $V$ and edges $E$ where $|V|=n$. The
edges in set $E$ may have weights or be unweighted, and we mainly focus on the
former case, and state it explicitly when this is not the case. The length of
a path is determined by the number of edges in the path when $E$ is
unweighted, and by the total weight of the edges in the path when $E$ is
weighted. The diameter of the graph $G$, denoted $D$, is the maximum distance
between any two nodes in $V$, i.e., $D=\max_{u,v\in V}\textnormal{d}(u,v)$.
For any node $u\in V$, the eccentricity is $\textnormal{ecc}(u)=\max_{v\in
V}\textnormal{d}(u,v)$, so we also have $D=\max_{u\in V}\textnormal{ecc}(u)$.

Let $k\in\mathbb{N}$ be a given parameter. In the $k$-center problem, we aim
to find a set $S^{*}\subseteq V$ with a size of at most $k$ that minimizes the
maximum distance of any node of $V$ to its nearest center in $S$. More
formally, we seek a set $S^{*}$ with $|S^{*}|\leq k$ that minimizes the value
$\max_{v\in V}{\min_{s\in S^{*}}\textnormal{d}(v,s)}$. This value is denoted
as $\textnormal{OPT}_{k}(G)$ or simply $\textnormal{OPT}_{k}$ when the context
is clear. For $\alpha\geq 1$, an algorithm is considered
$\alpha$-approximation if it can compute a solution $S$ such that the distance
of any node $v\in V$ to its nearest node in $S$ is at most
$\alpha\cdot\textnormal{OPT}_{k}$.

###  2.2 Computational Models

We consider three common computational models for studying distributed graph
algorithms, namely the local, congest and clique models. We model a
communication network using its graph, with nodes representing computational
units and edges representing communication links. We use $n$ for the number of
nodes (computational units) and assume they have unique ids in
$\\{1,\ldots,n\\}$ (specifically, there is always a node with id 1). The
computation proceeds in synchronous rounds, where in each round each node
sends messages to its neighbors, receives messages form them, and updates its
local state accordingly. The input is local, in the sense that each node
initially knows only its id, list of neighbors, and if there are inputs such
as edge weights, then also the weights of its incident edges. The outputs are
similarly local, e.g., at the end of the algorithm’s execution each node
should know if it is a center or not.

In the local model [27], the message sizes are unbounded, and an $r$-round
algorithm is equivalent to having each node deciding by its distance-$r$
neighborhood [22]. The congest model [28, 10] is similarly defined, but each
node is limited to sending $O(\log n)$-bit messages to each of its neighbors
in each round, where messages to different neighbors might be different from
one another. This model allows each node to send, e.g., its id or the ids of
some of its neighbors in a single round, but not its full list of neighbors. A
common primitive in this model is that of construction a BFS tree from a node.
This is sometimes extended to multiple BFS trees, or trees of bounded depth.
See, e.g., [21, 17].

Finally, we model a network with a congested all-to-all overly network by the
clique model [23, 13]. In this model, the input is a network as before, but
the communication is less limited: in each round, each node can send $O(\log
n)$-bit messages to each other node in the graph, and not only to its
neighbors. This allows the nodes, e.g., to re-distribute the inputs in
constant time [11, 20], and compute all-pairs-shortest-paths in sub-linear
time [5].

###  2.3 Communication Complexity

We prove lower bounds for the $k$-center problem in the congest model using a
reduction to _communication complexity_ , a well-studied topic in theoretical
computer science [19, 30].

In the two-party _set disjointness_ (henceforth: disjointness) communication
complexity problem, two players referred to as Alice and Bob get two
$\ell$-bit strings $x$ (Alice’s string) and $y$ (Bob’s string), and
communicate by exchanging messages on a reliable asynchronous channel. Their
goal is to decide if the sets represented by the indicator vectors $x$ and $y$
are disjoint or not, i.e., if there is an index $i$ such that $x[i]=y[i]=1$,
in which case we say they are not disjoint and the players must output $0$, or
otherwise, the sets are disjoint and they should output $1$.

Alice and Bob follow some protocol indicating who should send messages at each
step and what message to send. The communication complexity of a protocol (as
a function of $\ell$ is the maximal number of bits they exchange when
executing it, and the deterministic communication complexity of a problem the
the minimal communication complexity of a protocol solving the problem. The
randomized communication complexity is similarly defined, but the players may
also use random bits when executing the protocol, and the success probability
is at least $2/3$, when taken on the choice of random bits.

For the disjointness problem, there is an $\Omega(\ell)$ lower bound, which
holds for deterministic and randomized algorithms alike [19, Example 3.22].

###  2.4 Related Work

To our surprise, the $k$-center problem was not studied in traditional
distributed computing models. We survey below works in related computational
models, and works on the related problem of metric facility location in
distributed settings.

####  2.4.1 $k$-Center in Related Computational Models

Bandyapadhyay, Inamdar, Pai, and Pemmaraju [2] studied the $k$-center problem,
along with the related uncapacitated facility location and $k$-median
problems. They consider the $k$-machine model (the parameter $k$ here need not
be the same as in $k$-center) which is closely related to the clique model. As
mentioned, their work implies a randomized $(2+\epsilon)$-approximation
$O(\operatorname{poly}\log n)$-time $k$-center algorithm in the clique model.
Chiplunkar, Kale, and Ramamoorthy [8] studied approximate $k$-center in
_streaming_ models, and also in a parallel model where multiple processors
perform local computations and then send the results to a central processor.
Surprisingly, these seem to be the only works on the $k$-center problem in
distributed settings. Cruciani, Forster, Goranci, Nazari, and Skarlatos [9]
recently studied the $k$-center problem in a centralized _dynamic graphs_
setting.

####  2.4.2 Metric Facility Location

The metric facility location problem has attracted more attention in
distributed settings than the $k$-center problem. Works on this problem
consider models that share similarities with the ones we consider here,
although typically the models are not precisely identical.

##### The congest Model

In an unpublished manuscript, Briest, Degener, Kempkes, Kling, and Pietrzyk
[4] studied metric facility location in the congest model. They focused on a
bipartite graph, with one side representing facilities and the other
representing clients. Some of their results appeared in the thesis of Pietrzyk
[29]. This work improved upon previous work that also consider metric facility
location in bipartite setting in the congest model [26, 25].

##### The clique Model

Gehweiler, Lammersen, and Sohler [14] studied metric facility location in a
model resembling the clique. They present a $3$-round randomized algorithm
that gives a constant approximation factor, based on the method of Mettu and
Plaxton [24].

##### Distributed Large-Scale Computational Models

Inamdar, Pai, and Pemmaraju [18] studied metric facility location in the
clique model, MPC and $k$-machine, and gave an $O(1)$-approximation algorithm
using a Mettu-Plaxton-style algorithm. When considering the clique model with
what they call “implicit metric”, their model coincides with ours. They also
consider another input regime (“explicit metric”), but not in the local and
congest models, and not for the $k$-center problem. Their work improves upon
earlier works on metric facility location in the clique model [16, 3].

##  3 The $k$-Center Problem in the local Model

In this section, we consider the $k$-center problem in the local model. We
start with a fast and simple $((2+\epsilon)k)$-approximation algorithm,
Algorithm 1.

######  Lemma 1.

For any $\epsilon>0$ there is a deterministic $O(k/\epsilon)$-round algorithm
in the local model that gives a $((2+\epsilon)k)$-approximate solution for the
$k$-center problem.

Algorithm 1 A $((2+\epsilon)k)$-approximation in the local model

1:$t\leftarrow 2+\frac{4}{\epsilon}$

2:Perform a BFS from $v_{1}$ for $tk$ rounds

3:Report back on the tree if terminated on all branches under you

4:if All branches terminated then

5: Aggregate all the graph to $v_{1}$

6: Locally compute an optimal solution

7: Disseminate the solution on the BFS tree

8:else Only $v_{1}$ marks itself as a center

###### Proof.

Let $t=2+\frac{4}{\epsilon}$. The algorithm starts by having the node with id
$1$ (or any other arbitrary node) initiating the construction of a BFS tree of
depth $tk$. After $tk$ rounds, the nodes report back up the tree if the tree
construction algorithm terminated in all its branches (i.e., reached all the
nodes) or not. If it terminated, we have $D\leq tk$, and in another $O(tk)$
rounds node 1 can aggregate all the graph structure and find an optimal
solution. Otherwise, node 1 becomes the only center.

We claim that this simple algorithm gives a $(2+\epsilon)k$ approximate
solution; clearly, we only need to prove it for the case $D>tk$. The
eccentricity of node 1 is at most $D$, which gives an upper bound on ALG, the
quality of the solution given by the algorithm.

Recall that $\textnormal{OPT}_{k}$ is the largest distance from a node to its
center in an optimal solution. Let $\pi$ be the shortest path between two
nodes of the largest distance, i.e., two nodes of distance $D$. In an optimal
solution, there are at least $D+1-k$ non-center nodes in $\pi$. Therefore,
there is a center that covers at least $(D+1-k)/k$ nodes of $\pi$. Hence,
$\textnormal{OPT}_{k}$ is at least $(D+1-k)/(2k)=D/2k+1/2k-1/2\geq D/2k-1$.

Note that $D>tk$ implies $D/(tk)>1$. The approximation ratio is thus

$\frac{\textnormal{ALG}}{\textnormal{OPT}_{k}}\leq\frac{D}{D/2k-1}\leq\frac{D}{D/2k-D/(tk)}=\frac{2tk}{t-2}=(2+\epsilon)k$

by the choice of $t$, as required. ∎

This algorithm utilizes the fact that local computation is not limited in the
local model, so $v_{1}$ can find an optimal solution. However, it is not
strictly necessary to use all this computational power: in case $v_{1}$ has to
locally solve $k$-center, it can instead compute a $2$-approximation in a
greedy manner. The approximation ratio is still as required, and the local
computation now takes polynomial time.

Next, we move to the main result of the section: a lower bound for the
$k$-center problem in the local model. Our lower bound also works for bi-
criteria algorithms, which return at most $\beta k$ centers instead of at most
$k$ centers, for some $\beta\geq 1$; if the algorithm returns at most $k$
centers, we can simply set $\beta=1$. Our lower bound states that any
$t$-round algorithm cannot achieve an approximation ratio better than
$k-\frac{k^{2}+k(\beta k-1)(2t+1)}{n+k}$. If $k^{2}+k(\beta k-1)(2t+1)<n+k$
holds, then our lower bound states that it is not possible to get an
approximation ratio better than $k-1$. The typical case is the non-bi-criteria
one, with $k$ being a constant, and there our lower bound translates to
stating that getting an approximation ratio better than $k-1$ requires linear
time.

######  Theorem 1.

Let $t,k\in\mathbb{N}$, $\beta\geq 1$. Any $t$-round bi-criteria deterministic
local algorithm that solves the $k$-center problem and reports at most $\beta
k$ centers as the solution, cannot have an approximation ratio better than
$k-\frac{k^{2}+k(\beta k-1)(2t+1)}{n+k}$, where $n>2\beta kt$ is the size of
the graph and $\beta\geq 1$.

At a high-level, the proof considers a communication graph which is a cycle,
an algorithm in the local model that is faster than the lower bound, and the
centers chosen by it. In $t$ rounds, each node (and specifically, each chosen
center) can gather information only from a segment of $2t+1$ nodes. We thus
create a new cycle by concatenating all the $(2t+1)$-node segments around the
chosen centers. By the choice of the parameters, this leaves some “leftover
nodes” that are not in any segment, which are concatenated after all the
segments. When executing the same algorithm on the new cycle, the same nodes
as before will become centers, as they gather exactly the same information.
The “leftover nodes” are now far from all the chosen centers, rendering a bad
approximation ratio, as claimed.

###### Proof.

Let $\mathcal{A}$ be an algorithm that finds an (approximate, bi-criteria)
solution for the $k$-center problem. Let $k^{\prime}\leq\beta k$ be the
maximum number of centers that $\mathcal{A}$ reports for any cycle of length
$n$, and let $C$ be such a cycle. For simplicity, we label the nodes of $C$
with numbers $1,\ldots,n$ in a clockwise order. Assume that
$c_{1}<\ldots<c_{k^{\prime}}$ are the centers returned by $\mathcal{A}$ in
clockwise order. Since $n>2kt$, there exists at least two consecutive centers
such that the distance between them is more than $2t$. We introduce a new
cycle $C^{\prime}$ by re-arranging the nodes and show that the solution that
$\mathcal{A}$ finds for $C^{\prime}$ has an approximation ratio of at least
$k-\frac{k^{2}+k(\beta k-1)(2t+1)}{n+k}$.

To build the cycle $C^{\prime}$, we first define segments
$S_{1},\ldots,S_{k^{\prime}}$ of $C$ as follows. Each segment $S_{i}$ is of
the form $S_{i}=[b_{i},e_{i}]$, which refers to the nodes $b_{i}$ to $e_{i}$
in the clockwise order. Roughly speaking, each $S_{i}$ is a segment of $2t+1$
nodes centered around $c_{i}$, but since such segments might overlap, the
exact definition is a bit more subtle.

We define $e_{i}:=\min(c_{i}+t,c_{i+1}-1)$ for any $1\leq i<k^{\prime}$ and
$e_{k^{\prime}}:=\min(c_{k^{\prime}}+t,n+c_{1}-1)$. We also define
$b_{1}:=\max(c_{1}-t,n-c_{k^{\prime}}+1)$ and $b_{i}:=\max(c_{i}-t,e_{i-1}+1)$
for any $1<i\leq k^{\prime}$. Note that $e_{k}$ may be larger than $n$, in
which case we consider $S_{k^{\prime}}$ as the segment starting at $b_{i}$ and
ending at $e_{k^{\prime}}-n$ in the clockwise order, i.e.
$S_{k^{\prime}}=[b_{k^{\prime}},n]\cup[1,e_{k^{\prime}}-n]$. Similarly,
$b_{1}$ might be smaller than $1$, in which case we consider nodes $b_{1}+n$
to $e_{1}$ in the clockwise order, i.e. $S_{1}=[b_{1}+n,n]\cup[1,e_{1}]$.

Since we assumed $n>2\beta kt$, then there is an $i^{*}$ such that the
distance between $c_{i^{*}}$ and $c_{i^{*}+1}$ is more than $2t$ (we consider
$c_{1}$ as $c_{i^{*}+1}$ if $i^{*}=k^{\prime}$). To build $C^{\prime}$, we
concatenate the segments $S_{i^{*}+1},S_{i^{*}+2},\ldots,S_{k}$ followed by
$S_{1},S_{2},\ldots,S_{i^{*}}$, and finally all the remaining nodes of $C$, in
a clockwise order (see Figure 1).

Figure 1: Illustration for the proof of Theorem 1. Left: cycle $C$. Right:
cycle $C^{\prime}$

Now, we claim that there is an execution of $\mathcal{A}$ on $C^{\prime}$ that
reports $c_{1},\ldots,c_{k^{\prime}}$ as the centers. Since the distance
between $c_{i^{*}}$ and $c_{i^{*}+1}$ is more than $2t$, then the
neighbourhood of length $t$ for the nodes $c_{i^{*}}$ and $c_{i^{*}+1}$ is
disjoint. Along with the definition of the segments, we can conclude that the
distance-$t$ neighborhood for any node $c_{i}$ is the same in both $C$ and
$C^{\prime}$. Hence, any node $c_{i}$ receives the same information for both
graphs $C$ and $C^{\prime}$, and therefore, each node $c_{i}$ makes the same
decisions. Since $c_{1},\ldots,c_{k}$ chose to be the centers in $C$, they
also chose to be the centers in $C^{\prime}$. Moreover, we assumed that
$k^{\prime}$ is the maximum number of centers that $\mathcal{A}$ reports for a
cycle of length $n$, and hence, no other node chooses to be a center.

We next discuss the approximation ratio. According to the definition of
$S_{i}$, each $S_{i}$ is of size at most $2t+1$. Therefore, there are at most
$(k^{\prime}-2)(2t+1)$ nodes in
$S_{i^{*}+2},S_{i^{*}+3}\ldots,S_{k},S_{1},S_{2},\ldots,S_{i^{*}-1}$. Then, in
the clockwise path from $c_{i^{*}+1}$ to $c_{i^{*}}$ in $C^{\prime}$ there are
at most $(t+1)+(k^{\prime}-2)(2t+1)+(t+1)=(k^{\prime}-2)(2t+1)+2t+2$ nodes.
This means that the distance from $c_{i^{*}+1}$ to $c_{i^{*}}$ in $C^{\prime}$
in the anti-clockwise order is at least
$n-((k^{\prime}-2)(2t+1)+2t+2)+1=n-(k^{\prime}-1)(2t+1)$, and note that there
is no center in this path. Hence, there is a node in the anti-clockwise path
from $c_{i^{*}+1}$ to $c_{i^{*}}$ in $C^{\prime}$ such that its distance to
the nearest center is at least $(n-(k^{\prime}-1)(2t+1))/2$.

On the other hand, the optimal solution has
$\textnormal{OPT}_{k}\leq\lceil(n-k)/(2k)\rceil$. To see this, we can choose
the $k$ centers such that the distance between any two consecutive centers in
the clockwise order is $\lceil n/k\rceil$ or $\lfloor n/k\rfloor$. Thus,
$\textnormal{OPT}_{k}\leq\lceil(n-k)/(2k)\rceil$ holds and the approximation
ratio of Algorithm $\mathcal{A}$ is at least

$\displaystyle\frac{(n-(k^{\prime}-1)(2t+1))/2}{\lceil(n-k)/(2k)\rceil}\geq\frac{(n-(k^{\prime}-1)(2t+1))/2}{(n-k)/(2k)+1}=k\frac{n-(k^{\prime}-1)(2t+1)}{n-k+2k}$
$\displaystyle\quad\quad\quad=k-\frac{k^{2}+k(k^{\prime}-1)(2t+1))}{n+k}\geq
k-\frac{k^{2}+k(\beta k-1)(2t+1)}{n+k}\enspace,$

which finishes the proof. ∎

##  4 A $2$-Approximation in the congest Model

In this section, we show how to achieve a $2$-approximate $k$-center
clustering in the congest model in $O(kD)$ rounds, where $D$ is the diameter
of the underlying graph. Algorithm 2 presents an overview of our technique. In
the following, we explain each part of this algorithm in detail.

Algorithm 2 A $2$-approximation in the congest model

1:Find the node $v_{\min}$ with minimum id

2:$S\leftarrow\\{v_{\min}\\}$

3:for $k-1$ times do

4: Perform a BFS from all the nodes in $S$

5: Let $v^{*}$ be the furthest node from $S$, breaking ties by id

6: $S\leftarrow S\cup\\{v^{*}\\}$

7:Each node in $S$ marks itself as a center

As opposed to the local algorithm, here we do not need to use the assumption
that the nodes ids are in $\\{1,\ldots,n\\}$, and assuming they are taken from
$\\{1,\ldots,\operatorname{poly}n\\}$ suffices. The first step of Algorithm 2
is finding the node $v_{\min}$ with the minimum id, which can be done in
$O(D)$ rounds (and can be skipped if the ids are in $\\{1,\ldots,n\\}$). To do
this, we start a BFS from all nodes. In each round, each node may receive
messages of BFS trees from multiple sources. If this happens, such a node only
continue the BFS from the source with the minimum id it has seen so far, and
ignores the BFS’s for all other sources. Therefore, the only source that its
BFS is not paused after $D$ rounds is $v_{\min}$. Each leaf of a BFS tree
reports the termination of the construction up the tree, and back to the
tree’s parent. Hence, $v_{\min}$ becomes aware that it is the node with the
lowest id in $O(D)$ rounds. In another $O(D)$ time, $v_{\min}$ disseminates
along its BFS tree the depth of this tree, and all nodes learn this value, to
which we refer as $D^{\prime}$. Observe that $D^{\prime}\leq D<2D^{\prime}$,
and $2D^{\prime}$ will be used when an upper bound on $D$ is needed (e.g., for
the time of each iteration described below).

We next set $S=\\{v_{\min}\\}$, and preform $k-1$ iterations. In each
iteration, a BFS is performed, where the sources are all nodes in $S$. Each
node chooses to join the first BFS tree which reaches to it, breaking ties
arbitrarily. After $O(D)$ rounds, the BFS is done and each node knows its
distance to $S$. We next need to find the node with minimum id among the
furthest nodes to $S$, which we refer to it as $v^{*}$. This can be done in
$O(D)$ rounds. In each round, every node informs its neighbors which node has
the maximum distance among those it is currently aware of, and if it knows
more than one node with maximum distance, it only reports the one with the
smallest id. After $D^{\prime}$ such rounds, node $v^{*}$ knows that it is the
furthest node to $S$ with minimum id. Finally, $v^{*}$ can be added to $S$. At
the end of the algorithm, the nodes in $S$ mark themselves as centers.

The proof for the approximation ratio of our algorithm comes from the
approximation ratio of the known greedy approach by Gonzalez [15], which we
applied in our algorithm. In Lemma 2 we formally state this approximation.

######  Lemma 2 ([15]).

Let $G$ be a graph, and $k\geq 1$ be an integer. Assume $S_{1}={v_{1}}$, where
$v_{1}\in G$ is an arbitrary node. For each $1<i\leq k$, we have
$S_{i}=S_{i-1}\cup\\{v_{i}\\}$, where $v_{i}$ is a node of $G$ with maximum
distance to $S_{i-1}$. Then, $S_{k}$ is a $2$-approximate solution for
$k$-center of $G$.

We can now summarize this section in Theorem 2.

######  Theorem 2.

There exists a deterministic $2$-approximation algorithm for the $k$-center
problem in the congest model that needs $O(kD)$ communication rounds.

##  5 A Lower Bound in the congest Model

In this section, we show a lower bound on the number of communication rounds
for any algorithm for the $k$-center problem in the congest model with an
approximation ratio better than $4/3$. We start with a lower bound for the
$1$-center problem and then extend it for the $k$-center problem for a general
$k$.

###  5.1 A Lower Bound for the $1$-Center Problem

To prove the lower bound, we use a graph that was introduced by Abboud,
Censor-Hillel, Khoury, and Paz [1] in order to prove a lower bound for
computing the radius of a graph. Let $x$ and $y$ be two binary strings of
length $\ell$. The graph $G_{x,y}$ is built as follows, on $n=\Theta(\ell)$
nodes (see Fig. 2). On a high level, the graph consists of two main sets of
$\ell$ nodes each, $A$ and $B$, and a path on $4$ nodes:
$c_{A},\bar{c}_{A},c_{B},\bar{c}_{B}$. The input strings $x$ and $y$ for a
set-disjointness problem are used to set which edges from $A$ to $\bar{c}_{A}$
exist (representing $x$), and which edges form $B$ to $\bar{c}_{B}$ exist
(representing $y$). The rest of the graph is built in order to guarantee that
the optimal solution for the $1$-center problem, $\textnormal{OPT}_{1}$
satisfies $\textnormal{OPT}_{1}=4$ if and only if $x$ and $y$ are disjoint.
Hence, by simulating a $1$-center algorithm and finding the distance from the
chosen center to all other nodes, Alice and Bob can decide if $x$ and $y$ are
disjoint. Finally, if the algorithm is too fast, Alice and Bob can simulate it
with too little communication, contradicting the communication-complexity
lower bound for disjointness.

We now present the graph and the proof in detail. The graph $G_{x,y}$ consists
of node sets $A$, $B$, $F_{A}$, $T_{A}$, $F_{B}$, and $T_{B}$, as well as
nodes $c_{A}$, $\bar{c}_{A}$, $c_{B}$, and $\bar{c}_{B}$. The set $A$ is the
set of $\ell$ nodes $a^{0},a^{1},\ldots,a^{\ell-1}$ and the set $B$ is the set
of $\ell$ nodes $b^{0},b^{1},\ldots,b^{\ell-1}$. For $S\in\\{A,B\\}$, the set
$F_{S}$ consists of $\lfloor\log_{2}{\ell}\rfloor$ nodes
$f^{0}_{S},f^{1}_{S},\ldots,f^{\lfloor\log_{2}{\ell-1}\rfloor}_{S}$.
Similarly, the set $T_{S}$ contains node
$t^{0}_{S},t^{1}_{S},\ldots,t^{\lfloor\log_{2}{\ell-1}\rfloor}_{S}$. The edges
of the graph $G_{x,y}$ are described in the following.

  * •

Edges from $A$ to $F_{A}$ and $T_{A}$ and edges from $B$ to $F_{B}$ and
$T_{B}$. Let $0\leq i<\ell$ and $0\leq h<\ell$, and let
$\textnormal{bin}^{i}_{h}$ be the $h$-th bit in the binary representation of
$i$. If $\textnormal{bin}^{i}_{h}=0$, we connect $a^{i}$ to $f^{h}_{A}$ and we
connect $b^{i}$ to $f^{h}_{B}$. Otherwise, if $\textnormal{bin}^{i}_{h}=1$, we
connect $a^{i}$ to $t^{h}_{A}$ and we connect $b^{i}$ to $t^{h}_{B}$. That is
to say, we connect $a^{i}$ to the binary representation of $i$ in the sets
$F_{A}$ and $T_{A}$, where $F$ and $T$ represent “false” and “true”; $b^{i}$
is similarly connected.

  * •

Edges from $\bar{c}_{A}$ to $A$ and edge from $\bar{c}_{B}$ to $B$. For each
$0\leq i<\ell$, we connect $a^{i}$ to $\bar{c}_{A}$ if and only if $x[i]=1$,
and we connect $b^{i}$ to $\bar{c}_{B}$ if and only if $y[i]=1$.

  * •

Other edges from $c_{A}$, $\bar{c}_{A}$, $c_{B}$ and $\bar{c}_{B}$. We connect
$c_{A}$ to all nodes in $A$ and we connect $c_{B}$ to all nodes in $B$. We
also connect $\bar{c}_{A}$ to all nodes in $F_{A}$ and $T_{A}$, and similarly,
we connect $\bar{c}_{B}$ to all nodes in $F_{B}$ and $T_{B}$.

  * •

Edges between $F_{A}$, $T_{A}$, $F_{B}$, and $T_{B}$. For every $0\leq
h<\ell$, we connect $f^{h}_{A}$ to $t^{h}_{A}$ and $t^{h}_{B}$, and we connect
$t^{h}_{A}$ to $f^{h}_{B}$.

  * •

Edges from $w^{0}$, $w^{1}$ and $w^{2}$. We connect $w^{0}$ to all nodes in
$A$, and also $w^{0}$ to $w^{1}$ and $w^{1}$ to $w^{2}$.

Figure 2: Illustration of the graph $G_{x,y}$ [1]. The dotted edges depend on
the inputs for the disjointness problem.

Distances in the graph $G_{x,y}$ presented above have the following
properties.

######  Claim 1 ([1, Claim 4]).

Let $G_{x,y}$ be the graph defined above, and $V$ be the set of its nodes.
Then, the following holds

  1. 1.

For every node $u\in V\setminus A$, we have $\textnormal{ecc}(u)\geq 4$.

  2. 2.

For every node $a^{i}\in A$ and every $u\in V\setminus\\{b^{i},c_{B}\\}$ we
have $\textnormal{d}(a^{i},u)\leq 3$.

The first part of the claim holds since the distance of $w^{2}$ to any node in
$V\setminus A\cup\\{w^{0},w^{1},w^{2}\\}$ is at least $4$, and the distance of
$c_{B}$ to any node in $\\{w^{0},w^{1},w^{2}\\}$ is at least $4$. To show the
second part of the claim, observe that the distance between $a^{i}$ and any
node in $V\setminus B\cup\\{c_{B}\\}$ is clearly at most $3$. Besides, if
$j\neq i$, there exist $0\leq h<\ell$ such that
$\textnormal{bin}^{i}_{h}\neq\textnormal{bin}^{j}_{h}$, where
$\textnormal{bin}^{i}_{h}$ and $\textnormal{bin}^{j}_{h}$ are the $h$-th bit
in the binary representation of $i$ and $j$, respectively. If
$\textnormal{bin}^{i}_{h}=0$ and $\textnormal{bin}^{j}_{h}=1$, the path
$(a^{i},f^{h}_{A},t^{h}_{B},b^{j})$ exists. Otherwise, if
$\textnormal{bin}^{i}_{h}=1$ and $\textnormal{bin}^{j}_{h}=0$, the path
$(a^{i},t^{h}_{A},t^{h}_{B},b^{j})$ exists. It means that
$\textnormal{d}(a^{i},b^{j})\leq 3$, and therefore, the second part of the
claim holds. The rigorous proof of this claim can be found in [1, Claim 4].

Recall that $x$ and $y$ are not disjoint if there is a $0\leq i<\ell$ such
$x[i]=y[i]=1$, and otherwise, they are disjoint. In Lemma 3, we show that
$\textnormal{OPT}_{1}(G_{x,y})=4$ if and only if $x$ and $y$ are disjoint.

######  Lemma 3.

If the strings $x$ and $y$ are disjoint then
$\textnormal{OPT}_{1}(G_{x,y})=4$. Otherwise,
$\textnormal{OPT}_{1}(G_{x,y})=3$.

###### Proof.

To prove the lemma, we first show that if $\textnormal{OPT}_{1}<4$, then an
optimal center of $G_{x,y}$ for the $1$-center problem is a node $a^{i}\in A$,
such that $x[i]=y[i]=1$. Assume that $\textnormal{OPT}_{1}<4$. Then Claim 1(1)
implies that the optimal center is in $A$. Let $a^{i}\in A$ be an optimal
center. Then, $\textnormal{d}(a^{i},b^{i})\leq 3$ should holds since we assume
$\textnormal{OPT}_{1}<4$. But $\textnormal{d}(a^{i},b^{i})\leq 3$ holds only
if $a^{i}$ is connected to $\bar{c}_{A}$ and $b^{i}$ is connected to
$\bar{c}_{B}$, which means $x[i]=y[i]=1$.

We next consider the case that $x$ and $y$ are disjoint. In this case, we have
$\textnormal{OPT}_{1}\geq 4$ since otherwise, our claim implies that there
exists $0\leq i<\ell$ such that $x[i]=y[i]=1$ and contradicts the disjointness
of $x$ and $y$. Hence, $\textnormal{OPT}_{1}\geq 4$ holds. On the other hand,
all nodes are within distance $4$ of $a^{0}$, and therefore,
$\textnormal{OPT}_{1}=4$.

Now, we consider the case that $x$ and $y$ are not disjoint. This means that
there exist $0\leq i<\ell$ such that $x[i]=y[i]=1$. We show that
$\textnormal{ecc}(a^{i})=3$ and then $\textnormal{OPT}_{1}=3$. Claim 1(2)
states that $\textnormal{d}(a^{i},u)\leq 3$ holds for any $u\in
V\setminus\\{b^{i},c_{B}\\}$. Besides, $a^{i}$ is connected to $\bar{c}_{A}$
as $x[i]=1$ and $b^{i}$ is connected to $\bar{c}_{B}$ since $y[i]=1$. Thus,
$\textnormal{d}(a^{i},b^{i})=\textnormal{d}(a^{i},c_{B})=3$. Putting
everything together we have $\textnormal{OPT}_{1}=3$. ∎

######  Theorem 3.

Any congest algorithm that returns an $\alpha$-approximation for the
$1$-center problem with $\alpha<4/3$, even randomized, must take
$\Omega(n/\log^{2}n)$ rounds to complete.

###### Proof.

Assume for contradiction a congest algorithm faster than in the theorem’s
statement. Let $x,y\in\\{0,1\\}^{\ell}$ be two inputs of Alice and Bob for the
disjointness problem. Alice and Bob simulate the algorithm on the graph
$G_{x,y}$ described above.

To this end, we split the graph node by $V_{A}=A\cup F_{A}\cup
T_{A}\cup\\{c_{A},\bar{C}_{a},w^{0},w^{1},w^{2}\\}$ and $V_{B}=V\setminus
V_{A}$ (the nodes on the left and right sides of Fig. 2, respectively). Alice
is in charge of the nodes of $V_{A}$ and Bob on $V_{B}$. To simulate a round,
they locally simulate the exchange of messages in each of their node sets, and
exchange bits to simulate the messages between nodes of $V_{A}$ and $V_{B}$.
Since there are $O(\log n)$ edges between the sets, a simulation of a round
requires $O(\log^{2}n)$ bits of communication.

If the output of the algorithm is a node not in $A$, Alice and Bob return $1$
for the disjointness problem. If it is some node $a^{i}\in A$, the exchange
the bits $x[i]$ and $y[i]$ (for the same index $i$) and return $0$ for the
disjointness problem if and only if $x[i]=y[i]=1$.

For correctness, first note that Alice and Bob return $0$ for the disjointness
problem only if they find an index such that $x[i]=y[i]=1$, so this answer
must be correct. When they return $1$, on the other hand, it might be since
the algorithm returned a center $u\notin A$, or a center $a^{i}$ such that
$x[i]=0$ or $y[i]=0$ (or both).

If Alice and Bob return $1$ because of a center $u\notin A$, then 1(1)
guarantees that $\textnormal{ecc}(u)\geq 4$, and by $\alpha<4/3$ we get that
$\textnormal{OPT}_{1}>3$. Have the sets not been disjoint, Lemma 3 guarantees
that $\textnormal{OPT}_{1}=3$, a contradiction.

If Alice and Bob return $1$ because of a center $a^{i}\in A$, then we also
know that $x[i]=0$ or $y[i]=0$. Note that $\textnormal{d}(a^{i},b^{i})\geq 4$:
the nodes of $\textnormal{bin}(a^{i})$ and $\textnormal{bin}(b^{i})$ are never
neighbors, so any $3$-path connecting $a^{i}$ and $b^{i}$ must go through the
edge $(\bar{c}_{A},\bar{c}_{B})$; but since $x[i]=0$ or $y[i]=0$, no such path
can exists. Hence, $\textnormal{ecc}(a^{i})\geq 4$. As before, if the sets
were not disjoint, Lemma 3 guarantees that $\textnormal{OPT}_{1}=3$, and we
would have got a contradiction.

For the complexity, let $T$ be the number of rounds used by the algorithm. To
simulate these rounds, Alice and Bob exchange $O(T\log^{2}n)$ bits. As shown
above, they solve the disjointness problem on $\ell$ bits, which requires them
to communicate $\Omega(\ell)$ bits, even when using a randomized algorithm. As
$\ell=\Theta(n)$, we get $T=\Omega(n/\log^{2}n)$. In fact, Alice and Bob must
also exchange the id of the node chosen as the center, but these $\log n$ bits
of communication do not affect the asymptotic complexity.

Finally, note that Alice and Bob cannot solve disjointness solely by the
output of the algorithm, and need extra communication after it. Hence, we
cannot utilize standard reductions such as [1, Theorem 6] and use a non-
standard one. ∎

###  5.2 Extending the Lower Bound to the $k$-Center Problem

To generalize the lower bound for the $1$-center problem to the $k$-center
problem, we consider $k$ copies of the graph $G_{x,y}$ introduced in Section
5.1, such that all copies share the node $w^{2}$. We refer to this graph as
$G^{k}_{x,y}$.

######  Claim 2.

In any $\alpha$-approximate solution for $k$-center of $G^{k}_{x,y}$,
$\alpha<3/2$, exactly one center is chosen from each copy.

###### Proof.

Note that Lemma 3 guarantees that in each copy we can choose a center and get
a solution with distance at most $4$ from each node to a center, and
$\textnormal{OPT}_{k}\leq 4$. If some copy contains no center, then $b^{0}$ in
this copy has distance at least $6$ to $w^{2}$, and the solution is at least
$(6/4)$-approximation, a contradiction. ∎

######  Theorem 4.

Any congest algorithm that returns an $\alpha$-approximation for the
$k$-center problem with $\alpha<4/3$, even randomized, must take
$\Omega(n/(k^{2}\log^{2}n))$ rounds to complete.

The proof extends the proof of Theorem 3 by using the graph $G^{k}_{x,y}$
described above. Note that all copies are for the same input pair $(x,y)$.

###### Proof.

Assume a faster algorithm than in the theorem statement. Alice and Bob
simulate this algorithm for $\ell$ input bits, where $\ell=\Theta(n/k)$, and
get an output at the form of $k$ center nodes. If none of the output nodes is
of the form $a^{i}\in A$ for some copy, Alice and Bob answer $1$ for the
disjointness problems. Otherwise, for every node $a^{i}\in A$ in the output
(perhaps from different copies), they exchange $x[i],y[i]$, and answer $0$ for
the disjointness problem only if $x[i]=y[i]=1$ for at least one such $i$.

For correctness, recall first that 2 guarantees that each copy contains
exactly one center.

If Alice and Bob answer $0$, this is because they found an index $i$ of
intersection and the algorithm is correct. If they answer $1$, the proof
follows the same lines of the proof of Theorem 3: if the sets are not disjoint
then Lemma 3 guarantees each copy has a center $a^{i}$ with
$\textnormal{ecc}(a^{i})\leq 3$, and we get $\textnormal{OPT}_{k}\leq 3$. On
the other hand, the algorithm returns at each copy a node $u\notin A$ or a
node $a^{i}$ with $x[i]=0$ or $y[i]=0$, which has
$\textnormal{d}(a^{i},b^{i})\geq 4$; in both cases, the solution is not an
$\alpha$-approximation for $\alpha<4/3$.

For the complexity, assume the algorithm takes $T$ rounds. Alice and Bob
communicate, for each copy and each round, $O(\log(n/k)\log n)$ bits, which
are $O(\log^{2}n)$ bits. At the end of the algorithm, they may exchange the
indices of at most $k$ centers of the form $a^{i}$ and their inputs $x[i]$ and
$y[i]$ in these locations, with takes requires another $O(k\log n)$ bits. In
total, they exchange $O(Tk\log^{2}n+k\log n)$ bits, which is $O(Tk\log^{2}n)$.

On the other hand, they solve disjointness on $\ell=\Theta(n/k)$ input bits,
so they must communicate $\Omega(n/k)$ bits. Hence,

$Tk\log^{2}n\geq cn/k$

for some constant $c$, and we get

$T=\Omega\left(\frac{n}{k^{2}\log^{2}n}\right)$

as claimed. ∎

##  6 A $2$-Approximation Algorithm in the clique Model

We now present Algorithm 3, which provides an approximate solution to the
$k$-center clustering problem in the clique model. It is applicable both when
the distance between the nodes are weighted and when they are unweighted.

The algorithm consists of two phases. The first phase is computing all-pairs
shortest distances or approximating them, using known algorithms.

The second phase is to greedily find the centers, which is done in additional
$k$ rounds. In this phase, we first find $v_{\min}$, the node with the minimum
id. This is trivial when the ids are in $\\{1,\ldots,n\\}$, but easy also
without this assumption, by having each node send its id to all other nodes.
We then set $S\leftarrow\\{v_{\min}\\}$. Next, we have $k-1$ iteration, and in
each iteration we find $v^{*}$, which is the furthest node from $S$ (if there
is more than one furthest node, we define $v^{*}$ as the furthest node with
minimum id). To accomplish this, it is enough that each node sends its
distance to $S$ to all nodes. Hence, all nodes can know who $v^{*}$ is in one
communication round. At the end of each iteration, we set $S$ to
$S\cup\\{v^{*}\\}$, and report $S$ as the set of centers at the end of the
algorithm. This process is formalized in the following algorithm.

Algorithm 3 Varying approximation ratios in the clique model

1:Compute all-pairs shortest paths

2:Let $v_{\min}$ be the node with minimum id

3:$S\leftarrow\\{v_{\min}\\}$

4:for $k-1$ times do

5: Let $v^{*}$ be the furthest node to $S$

6: $S\leftarrow S\cup\\{v^{*}\\}$

7:Each node in $S$ marks itself as a center

If we calculate the exact all-pairs shortest paths in the first phase of
Algorithm 3, Lemma 2 indicates that the set $S$ computed by the algorithm is a
$2$-approximate solution for $k$-center.

Approximate distance can be computed much faster than exact ones, and we next
show that Algorithm 3 can also work with approximate distances, in which case
it computes an approximate $k$-center solution. To prove this, we now prove
Lemma 4, which extends Lemma 2 to the scenario where only a multiplicative
$\alpha$-approximation with one-sided error of all-pairs shortest paths is
computed in the first phase.

######  Lemma 4.

For any $\alpha\geq 1$, if an $\alpha$-approximation of all-pairs shortest
paths is computed in the first phase of Algorithm 3, then the set $S$ obtained
by the algorithm is a $(2\alpha)$-approximate solution for the $k$-center
problem.

###### Proof.

If $n\leq k$, the algorithm trivially returns all the nodes as the centers, so
we assume $n>k$ in the following. Let $S$ be the set returned by Algorithm 3,
$\hat{v}\in V\setminus S$ the furthest node from $S$, and $\hat{r}$ its
distance.

First, we claim that $\textnormal{OPT}_{k}\geq\hat{r}/(2\alpha)$. Since
$\hat{v}$ is not added to $S$, we can conclude that the distance between any
two nodes in $S$ is at least $\hat{r}/\alpha$. Thus, the distance between any
two nodes in $S\cup\\{\hat{v}\\}$ is at least $\hat{r}/\alpha$ as well. In
addition, in any optimal solution there exist two nodes in
$S\cup\\{\hat{v}\\}$ that have the same nearest center in that optimal
solution since $|S\cup\\{\hat{v}\\}|=k+1$. Since the distance between these
two nodes is at least $\hat{r}/\alpha$, at least one of them has distance at
least $\hat{r}/(2\alpha)$ from their common center, implying
$\textnormal{OPT}_{k}\geq\hat{r}/(2\alpha)$. On the other hand, all nodes in
$V$ are within distance $\hat{r}$ from $S$ by the definition of $\hat{r}$.
Hence, $S$ is a solution with the approximation ratio of at most
$\frac{\hat{r}}{\hat{r}/(2\alpha)}=2\alpha$. ∎

All is left now is to plug fast clique distance computation algorithms [7, 6,
12, 5] in the lemma, and we get fast algorithms for exact and approximate
$k$-center. This yields the results detailed in Theorem 5 and Table 1, showing
that $k$-center can be approximated in the same times as all pairs shortest
paths computation, up to an additive $O(k)$ time. Note that for the specific
case of $(2+\epsilon)$-approximation, a much faster (randomized) algorithm
exists [2], running in $O(\operatorname{poly}\log n)$ rounds.

######  Theorem 5.

There exists a deterministic clique algorithm for the $k$-center problem which
gives a $2$-approximation in $O(n^{1/3}+k)$ rounds on weighted graphs and
$O(n^{0.158}+k)$ rounds on unweighted graphs.

For every constant $0<\epsilon<1$, there exist deterministic algorithms that
give a $(2+\epsilon)$-approximation in $O(n^{0.158}+k)$ rounds on unweighted
graphs, a $(4+\epsilon)$-approximation in $O(\log^{4}\log n+k)$ rounds on
unweighted graphs, and a $(6+\epsilon)$-approximation in $O(\log^{2}n+k)$
rounds on weighted graphs.

There exists a randomized algorithm which gives a $O(\log n)$-approximation in
$O(k)$ rounds on both weighted and unweighted graphs.

Table 1: Approximation times in the clique model, for constant $0<\epsilon<1$ Approx. ratio | Time | Weighted? | Deter.? | Ref.
---|---|---|---|---
2 | $O(n^{1/3}+k)$ | No | Yes |  [5] & Thm. 5
2 | $O(n^{0.158}+k)$ | Yes | Yes |  [5] & Thm. 5
$2+\epsilon$ | $O(n^{0.158}+k)$ | No | Yes |  [5] & Thm. 5
$2+\epsilon$ | $O(\operatorname{poly}\log n)$ | Yes | No | [2]
$4+\epsilon$ | $O(\log^{4}\log n+k)$ | No | Yes |  [12] & Thm. 5
$6+\epsilon$ | $O(\log^{2}n+k)$ | Yes | Yes |  [6] & Thm. 5
$O(\log n)$ | $O(k)$ | Yes | No |  [7] & Thm. 5

#### Acknowledgments

We thanks Morteza Monemizadeh for many valuable conversations on this project,
Michal Dory for discussions regarding distance computation in the clique
model, and the anonymous reviewers of SIROCCO’24 for their helpful comments.

## References

  * Abboud et al. [2021] A. Abboud, K. Censor-Hillel, S. Khoury, and A. Paz.  Smaller cuts, higher lower bounds.  _ACM Trans. Algorithms_ , 17(4):30:1–30:40, 2021.  doi: 10.1145/3469834.  URL https://doi.org/10.1145/3469834.
  * Bandyapadhyay et al. [2022] S. Bandyapadhyay, T. Inamdar, S. Pai, and S. V. Pemmaraju.  Near-optimal clustering in the _k_ -machine model.  _Theor. Comput. Sci._ , 899:80–97, 2022.
  * Berns et al. [2012] A. Berns, J. Hegeman, and S. V. Pemmaraju.  Super-fast distributed algorithms for metric facility location.  In _ICALP (2)_ , volume 7392 of _Lecture Notes in Computer Science_ , pages 428–439. Springer, 2012.
  * Briest et al. [2011] P. Briest, B. Degener, B. Kempkes, P. Kling, and P. Pietrzyk.  A distributed approximation algorithm for the metric uncapacitated facility location problem in the congest model.  _CoRR_ , abs/1105.1248, 2011.
  * Censor-Hillel et al. [2019] K. Censor-Hillel, P. Kaski, J. H. Korhonen, C. Lenzen, A. Paz, and J. Suomela.  Algebraic methods in the congested clique.  _Distributed Comput._ , 32(6):461–478, 2019.
  * Censor-Hillel et al. [2021] K. Censor-Hillel, M. Dory, J. H. Korhonen, and D. Leitersdorf.  Fast approximate shortest paths in the congested clique.  _Distributed Comput._ , 34(6):463–487, 2021.
  * Chechik and Zhang [2022] S. Chechik and T. Zhang.  Constant-round near-optimal spanners in congested clique.  In _PODC_ , pages 325–334. ACM, 2022.
  * Chiplunkar et al. [2020] A. Chiplunkar, S. S. Kale, and S. N. Ramamoorthy.  How to solve fair k-center in massive data models.  In _ICML_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 1877–1886. PMLR, 2020.
  * Cruciani et al. [2024] E. Cruciani, S. Forster, G. Goranci, Y. Nazari, and A. Skarlatos.  Dynamic algorithms for k-center on graphs.  In _Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 3441–3462. SIAM, 2024.
  * Das Sarma et al. [2012] A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer.  Distributed verification and hardness of distributed approximation.  _SIAM J. Comput._ , 41(5):1235–1265, 2012.
  * Dolev et al. [2012] D. Dolev, C. Lenzen, and S. Peled.  "tri, tri again": Finding triangles and small subgraphs in a distributed setting - (extended abstract).  In _DISC_ , volume 7611 of _Lecture Notes in Computer Science_ , pages 195–209. Springer, 2012.
  * Dory and Parter [2022] M. Dory and M. Parter.  Exponentially faster shortest paths in the congested clique.  _J. ACM_ , 69(4):29:1–29:42, 2022.
  * Drucker et al. [2014] A. Drucker, F. Kuhn, and R. Oshman.  On the power of the congested clique model.  In _PODC_ , pages 367–376. ACM, 2014.
  * Gehweiler et al. [2014] J. Gehweiler, C. Lammersen, and C. Sohler.  A distributed o(1)-approximation algorithm for the uniform facility location problem.  _Algorithmica_ , 68(3):643–670, 2014.
  * Gonzalez [1985] T. F. Gonzalez.  Clustering to minimize the maximum intercluster distance.  _Theor. Comput. Sci._ , 38:293–306, 1985.  doi: 10.1016/0304-3975(85)90224-5.  URL https://doi.org/10.1016/0304-3975(85)90224-5.
  * Hegeman and Pemmaraju [2015] J. W. Hegeman and S. V. Pemmaraju.  Sub-logarithmic distributed algorithms for metric facility location.  _Distributed Comput._ , 28(5):351–374, 2015.
  * Holzer and Wattenhofer [2012] S. Holzer and R. Wattenhofer.  Optimal distributed all pairs shortest paths and applications.  In _PODC_ , pages 355–364. ACM, 2012.
  * Inamdar et al. [2018] T. Inamdar, S. Pai, and S. V. Pemmaraju.  Large-scale distributed algorithms for facility location with outliers.  In _OPODIS_ , volume 125 of _LIPIcs_ , pages 5:1–5:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * Kushilevitz and Nisan [1997] E. Kushilevitz and N. Nisan.  _Communication Complexity_.  Cambridge University Press, New York, NY, USA, 1997.  ISBN 0-521-56067-5.
  * Lenzen [2013] C. Lenzen.  Optimal deterministic routing and sorting on the congested clique.  In _Proc. 32nd ACM Symposium on Principles of Distributed Computing (PODC 2013)_ , pages 42–50, 2013.  doi: 10.1145/2484239.2501983.
  * Lenzen et al. [2019] C. Lenzen, B. Patt-Shamir, and D. Peleg.  Distributed distance computation and routing with small messages.  _Distributed Comput._ , 32(2):133–157, 2019.
  * Linial [1992] N. Linial.  Locality in distributed graph algorithms.  _SIAM J. Comput._ , 21(1):193–201, 1992.
  * Lotker et al. [2003] Z. Lotker, E. Pavlov, B. Patt-Shamir, and D. Peleg.  MST construction in o(log log n) communication rounds.  In _SPAA_ , pages 94–100. ACM, 2003.
  * Mettu and Plaxton [2003] R. R. Mettu and C. G. Plaxton.  The online median problem.  _SIAM J. Comput._ , 32(3):816–832, 2003.
  * Moscibroda and Wattenhofer [2005] T. Moscibroda and R. Wattenhofer.  Facility location: distributed approximation.  In _PODC_ , pages 108–117. ACM, 2005.
  * Pandit and Pemmaraju [2009] S. Pandit and S. V. Pemmaraju.  Return of the primal-dual: distributed metric facility location.  In _PODC_ , pages 180–189. ACM, 2009.
  * Peleg [2000] D. Peleg.  _Distributed Computing: A Locality-sensitive Approach_.  Society for Industrial and Applied Mathematics, 2000.  ISBN 0-89871-464-8.
  * Peleg and Rubinovich [2000] D. Peleg and V. Rubinovich.  Near-tight lower bound on the time complexity of distributed MST construction.  _SIAM Journal on Computing_ , 30(5):1427–1442, 2000.  doi: 10.1137/S0097539700369740.
  * Pietrzyk [2013] P. Pietrzyk.  _Local and online algorithms for facility location_.  PhD thesis, University of Paderborn, 2013.
  * Rao and Yehudayoff [2020] A. Rao and A. Yehudayoff.  _Communication Complexity: and Applications_.  Cambridge University Press, 2020.  ISBN 9781108497985.


# Revised performance parameters of the ZEPLIN-III dark matter experiment

Henrique Araújo111email<EMAIL_ADDRESS>on behalf of the ZEPLIN-III
Collaboration  High Energy Physics Group, Department of Physics, Imperial
College London, UK

###### Abstract

This note presents revised detector parameters applicable to data from the
First Science Run of the ZEPLIN-III dark matter experiment; these datasets
were acquired in 2008 and reanalised in 2011. This run demonstrated electron
recoil discrimination in liquid xenon at the level of 1 part in 10,000 below
40 keV nuclear recoil energy, at an electric field of 3.8 kV/cm; this remains
the best discrimination reported for this medium to date. Building on relevant
measurements published in recent years, the calibration of the scintillation
and ionisation responses for both electron and nuclear recoils, which had been
mapped linearly to 57Co $\gamma$-ray interactions, is converted here into
optical parameters which are better suited to relate the data to the emerging
liquid xenon response models. Additional information is given on the fitting
of the electron and nuclear recoil populations at low energy. The aim of this
note is to support the further development of these models with valuable data
acquired at high field.

##  1 Introduction

The ZEPLIN-III dark matter search experiment operated at the Boulby
Underground Laboratory (UK) in the period 2008–2011. This pioneering liquid
xenon time projection chamber (LXe-TPC) produced competitive results for
various scattering interactions [1, 2, 3, 4]. In particular, it achieved the
best electron recoil discrimination reported in this technology to date,
operating at an electric field approaching 4 kV/cm. The First Science Run
(FSR) of the experiment consisted of 67 live days of data acquired in 2008;
main results were presented in Ref. [1], hereafter ‘paper 1’. If the
parameters set out in this note are used it would be appropriate to cite Ref.
[1] to credit the experimental work as well as this note for explanation of
the new parameters. The instrument was upgraded with lower background
photomultiplier tubes (PMTs) for a Second Science Run (SSR), but the optical
performance of the instrument was degraded (leading to poorer discrimination)
[4]. The FSR dataset was therefore the more valuable one for further studies.

At the time of those results a microscopic model for the response of liquid
xenon (LXe) to low-energy particle interactions was still outstanding [5], and
results from this and other contemporaneous experiments were not presented in
a way that would make them immediately useful today, especially in what
concerns energy calibration. Major progress has been made since to understand
the mechanisms underlying the scintillation and ionisation responses in this
technology, in terms of the respective yields and their fluctuations for
electron and nuclear recoil interactions, and the discrimination between them.
These enabled the development of an accurate microscopic model for the
response of LXe to those interactions, incorporated into the Noble Element
Simulation Technique (NEST) [6]. The behaviour of those quantities at high
field is an important piece of the puzzle, yet to be fully understood [7].

At the core of the new microscopic model is a common “$W$-value” for the
production of quanta of scintillation and ionisation for electron recoil
interactions; for nuclear recoils, it is commonly considered that a Lindhard
factor (${\cal L}$) multiplies the energy deposited to estimate the energy
transferred to the electronic system of the colliding atoms, to which the
common $W$-value then applies (see, e.g. [8]. NEST can be used to predict the
number of scintillation photons and ionisation electrons escaping the
interaction site. In turn, the detector response to scintillation (S1) and
ionisation (S2) can be predicted if the photon detection efficiencies (PDE)
for the liquid and vapour phases are known: these are $g_{1}$ and $g_{1,gas}$,
representing the number of photons detected (phd) per photon emitted in the
liquid and in the gas phases, respectively; and $g_{2}$, representing the
number of detected photons per ionisation electron escaping the primary track.
These parameters are needed to relate the macroscopic S1 and S2 responses to
the microscopic model.

In this note a consistent set of response parameters is derived from those
published at the time, correcting the original results when more modern
measurements exist. In the published analyses the two channels were calibrated
relative to a reference – the 122.1 keV and 136.5 keV 57Co $\gamma$-rays – but
relating the measured S1 and S2 responses to the microscopic model does
require these additional PDE parameters. An example is the study of
discrimination in LXe just published by the LUX collaboration [7], which
includes results derived from ZEPLIN-III data in its Appendix A.

A reanalysis of the FSR datasets in 2011 corrected a fault in the original
determination of the nuclear recoil scintillation yield [9], and improved data
quality more generally through further development of the vertex
reconstruction algorithm [10]. These improved the energy resolution for 57Co
$\gamma$-rays from $\sigma$=5.4% to 3.6%. At low energy the discrimination
performance did not change appreciably. An equally important measurement was
the precise determination of the single electron response, which allowed
calibration of the electroluminescence response in FSR conditions [11]. In
this note the new parameters are derived from the reanalysed data, although in
most cases the original analysis described in paper 1 produced very similar
results.

##  2 Geometry and electric fields

ZEPLIN-III was a two-electrode xenon emission detector (no gate grid), with a
‘planar’ geometry viewed by a single PMT array immersed in the liquid phase.
The FSR operating pressure was 1.65 bar ($\pm$1%), corresponding to a liquid
temperature of 174.1 K. In the active region the nominal cathode-to-anode
separation was 40 mm, with the liquid level located a few mm below the anode
‘mirror’. The detector hardware is described in Ref. [12].

The gas gap between the liquid surface and the anode was 4.0$\pm$0.5 mm, and
the liquid height from the cathode was 36.0$\pm$0.5 mm, with errors dominated
by mechanical tolerance of the detector height. The diameter of the active
region was 386 mm, with the 6.5 kg analysis fiducial volume defined by a
radial cut at 150 mm and a vertical cut selecting 31.9 mm.

An updated calculation of the electric fields, using a somewhat lower
permittivity $\epsilon_{r}$=1.85 [13, 14] and considering field leakage
through the wire grids [15], lowers the field in the gas to 7.1 kV/cm, from
the original value of 7.8 kV/cm reported in paper 1. The field in the liquid
is 3.8 kV/cm, close to the original 3.9 kV/cm.

The thickness of the gas layer is a key parameter in determining the gain of
the S2 response. The liquid and gas heights were originally calculated from
capacitance sensor measurements and the electron drift velocities in the
liquid and gas phases. To understand if this can be calculated more precisely
than the 0.5 mm error assigned above the drift velocity in the liquid was
reassessed.

In the FSR the cathode was located at 14.1 $\mu$s drift time, with a slightly
higher value of 14.3 $\mu$s reported for the single-electron dataset in Ref.
[11]. The central value produces a drift speed of 2.53$\pm$0.05 mm/$\mu$s for
the nominal 36.0 mm liquid height. Taking the historical measurement of 2.83
mm/$\mu$s [16], corrected to the FSR operating temperature [17], gives 2.65
mm/$\mu$s. Systematic effects may account for this difference, including
cathode grid electrostatic deflection and the increased field near the cathode
wires, both of which would increase the drift speed slightly (these can be
determined with additional analysis). It is noted that somewhat lower values
were reported more recently [18], albeit for lower fields. It is concluded
that the gas gap cannot be determined more precisely than the 0.5 mm
uncertainty without additional data analysis.

##  3 Optical performance and energy calibration

The S1 and S2 energy scales were calibrated with 57Co $\gamma$-rays at 122.1
keV and 136.5 keV, averaging 124.5 keV into the LXe target from simulations
(see paper 1). The FSR calibration constants were 11.31 keVee/nVs for the S1
channel and 0.0289 keVee/nVs for the S2 channel. In this note, as in the
original publications, the unit ‘keVee’ is referenced to the equivalent S1 or
S2 signals produced by the 57Co response in each channel, for both electron
and nuclear recoils. The detector flat-fielding was referred to top-centre of
the liquid where most 57Co $\gamma$ rays interacted.

In this section the photon detection efficiencies and energy thresholds are
presented based on these calibration constants and additional parameters,
including calculation of primary quanta with NEST v2.0.1. In addition to the
single electron response determined at the time, key new measurements include
the electron emission probability from the liquid, the electroluminescence
yield in the cold vapour, and the double photoelectron emission (DPE) observed
in PMTs at VUV wavelengths [19].

The average DPE probability of the ETEL D730 PMTs was estimated to be 11%
averaged over the array, based on the comparison of the two single-electron
response distributions presented in Figure 2 of Ref. [11]. Dedicated
measurements of one such PMT in a recent study produced consistent results
[20]. In the latter reference it is noted that the novel method developed for
PMT calibration in ZEPLIN-III [21] in fact measured the mean of the single
photon response (47 pVs, as mentioned in paper 1) instead of the single
photoelectron response measured in the traditional way, which yielded a mean
pulse area of 41 pVs. This is consistent with the above DPE probability,
especially if applied to the more central PMTs.

The S1 PDE is calculated as $g_{1}$=0.0714$\pm$0.0031 phd per photon using the
scintillation yield given by NEST. This translates to an S1 light yield of
1.88 phd/keVee, which is close to the value stated in paper 1 (1.8 phe/keVee)
– noting that since the mean single photon response was used, the latter in
fact represents phd/keVee. The 4.3% discrepancy is given as the estimated
error in $g_{1}$.

The PDE of the gas phase can be obtained from the single electron response,
which was precisely measured to have a mean of 28.25$\pm$0.25 phd [11] and
width of 6.76 phd (Fano factor $F$=1.66). The number of emitted photons is
calculated from the electroluminescence yield data in cold vapour from Ref.
[22] parameterised by Eq. (4.9) in Ref. [5], which results in 254 photons per
emitted electron. This yields $g_{1,gas}$=0.111$\pm$0.003 phd per photon. It
is noted that in other detectors the $g_{1}$ and $g_{1,gas}$ are very similar,
but the planar geometry and all-copper construction of ZEPLIN-III motivate a
larger light collection efficiency from the gas phase: this is primarily due
to the focusing of the S2 light at the liquid surface and the placement of the
better PMTs towards the centre of the array.

The $g_{2}$ value, denoting the number of photons detected per ionisation
electron in the liquid, is obtained from the mean S2 response to 57Co divided
by the number of ionisation electrons estimated with NEST:
$g_{2}$=15.7$\pm$0.8 phd/e. The 5% error is dominated by the PMT calibration.

An key parameter to obtain a bottom-up model of the S2 response is the
electron emission probability – which has not been used to calculate the main
PDE parameters given above other than for consistency checks. Originally, a
value approaching 80% at the FSR field was used based on historical data [23],
which newer measurements confirmed to be a significant overestimation: recent
measurements [13] suggest 62%, and the latest results decrease this to
$\approx$57%. [14], which is the value adopted here. Although this parameter
was not required in the original analysis, it was used in the optical
simulation model, as mentioned below. Using the lower emission probability to
calculate the number of gas electrons, and hence the number of S2 photons
produced by 57Co $\gamma$-rays, we derive a $g_{1,g\\!a\\!s}$ which is $<$3%
away from the above value, which is a good consistency test; this discrepancy
is assigned as the error in the value presented above.

A detailed optical model was developed prior to the FSR [24]. Despite this
being reasonably sophisticated, it failed to match the data especially for the
S2 response. This is mostly due to the effects mentioned above, in particular
the overestimation of both the field in the gas and the emission probability
($\sim$60% combined effect). The remaining discrepancies for both S1 and S2
can be explained by the uncertainty in the reflectivity of copper at 175 nm,
which remains the case.

With the new PDE parameters NEST may be used to derive accurate NR and ER
energies, including the WIMP region of interest (ROI) and the detector
threshold. The FSR WIMP-search region was 2–16 keVee in S1, with the lower
bound corresponding approximately to the 50% efficiency onset of the S1
channel, determined by a 3-fold coincidence level. Using NEST the WIMP ROI
translates to 8.6–40.7 keV for NR and 2.4–12.3 keV for ER ($\beta$)
interactions. The NR range is close to that obtained from the reanalysis of
the NR scintillation yield in Ref. [9] (7–36 keV). The trigger threshold for
the main datasets corresponded to 11 ionisation electrons, as stated in paper
1; this was a broad threshold onset determined by hardware. A hard analysis
threshold was set at 5 nVs S2 pulse area, which translates to $\sim$4 emitted
electrons ($\approx$110 phd), or 7 ionisation electrons drifting in the liquid
using the above parameters (0.2 keVee in the 57Co S2 scale).

##  4 Discrimination

In the context of two-phase xenon detectors, ER-NR discrimination typically
refers to an integrated leakage from the ER band past the mean of the NR band,
with the latter defined through neutron calibration, integrated over some S1
region of interest. Modernly, this is purely a benchmark parameter that allows
different datasets or experiments to be compared, but in the ZEPLIN-III FSR
the ER leakage past the NR band mean was the estimator for the leading
background, and hence a key parameter. In the original FSR analysis a Feldman-
Cousins test statistic was applied to the ROI, and no shape information was
used.

Figure 1 shows the result of the 2011 reanalysis of the FSR dataset [25] from
which the discrimination was derived, by fitting these data – as well as the
neutron calibration – in 1 keVee wide bins in the 2–16 keVee ROI. The S1 and
S2 energy scales may be converted to phd units using the respective 57Co
calibration constants and the mean PMT response of 47 pVs/phd.

Figure 1: FSR dark data (2011 reanalysis) used to assess the discrimination of
ER events. The WIMP-search region spanned the
$\log_{10}(\mathrm{S2}/\mathrm{S1})$ range between $\mu_{NR}$ and
$\mu_{NR}-2\sigma_{NR}$ (green lines) in the range 2–16 keVee; 5 out of 38,877
events fall in this region, and a further 2 events are located below the lower
boundary. At higher energies, 25 events out of 113,067 fall below the NR mean.

The NR band was defined from Am-Be neutron calibration, with S1 bins fitted
with Gaussians in $x=\log_{10}(\mathrm{S2}/\mathrm{S1})$ space. The resulting
fits were parameterised in the range S1=1–40 keVee, giving an NR band mean and
width equal to $\mu_{NR}=\log_{10}(0.722\,{\mathrm{S}1}^{-0.483})$ and
$\sigma_{NR}=0.225\,{\mathrm{S}1}^{-0.405}$, respectively. The NR band mean
and the lower 2$\sigma$ boundary are shown in the figure.

The ER band was determined from the science data shown in this same figure,
which had a neutron background expectation of $\cal O$(1) event in the ROI. A
137Cs calibration, also discussed in paper 1, was found to slightly
overestimate the leakage due to PMT photocathode charging and accidental
coincidences. The ER population in the ‘dark’ data consisted mostly of low-
energy Compton scatters from PMT $\gamma$-rays which dominated the background
budget by a large factor.

In total, there were 38,877 events in the ROI, and the observed leakage in the
reanalysed dataset was 5 events in the WIMP acceptance region (cf. 7 events in
the original analysis). A further 2 events can be seen below the lower
boundary; these are discussed below.

As reported in paper 1 the Skew-Gaussian distribution was found to provide a
good description for shape of the ER band in
$\log_{10}(\mathrm{S2}/\mathrm{S1})$ space:

$S(x)=\frac{2A}{\omega\sqrt{2\pi}}e^{-\frac{(x-x_{0})^{2}}{2\omega^{2}}}\int_{-\infty}^{\alpha\frac{x-x_{0}}{w}}\frac{1}{\sqrt{2\pi}}e^{-\frac{t^{2}}{2}}dt\,,$

where $x_{0}$ and $\omega$ denote the mean and width of the Gaussian
component, $\alpha$ is the shape parameter, and $A$ is a normalisation
constant. The mean and standard deviation of the distribution are
$\mu=x_{0}+\omega\,\delta\,\sqrt{2/\pi}$ and
$\sigma=\omega\sqrt{1-2\delta^{2}/\pi}$, with
$\delta=\alpha/\sqrt{1+\alpha^{2}}$.

Skew-Gaussian parameters are given in Table 1 at the end of this document for
fits over the range $x=[-\infty,\,\mu_{ER}+\sigma_{ER}]$. Results up to the
12–13 keVee bin are very similar if one includes the full domain; however, the
quality of the fit to the critical lower tail deteriorates somewhat by forcing
the upper tail to be fully described. From the fitting, the predicted leakage
fraction is $1.7\times 10^{-4}$, with calculated error of 70%, which is
consistent with the observed leakage of $1.3\times 10^{-4}$ and 44% Poisson
error. The leakage is $1\times 10^{-4}$ or lower up to $\sim$12 keVee,
increasing to nearly $1\times 10^{-3}$ by 15 keVee.

It is likely that a small number of events below the NR mean is not due to
regular ER interactions. Aside from the small NR background from neutrons, the
most challenging background topology in the experiment was due to Multiple-
Scintillation Single-Ionisation (MSSI) events, which had been predicted even
before the instrument had operated [24]: the planar geometry was not
favourable to reject these interactions, in which, for example, a PMT
$\gamma$-ray scattered once in the LXe below the cathode and once in the
active region, producing interactions with a low S2/S1 ratio. It is possible
that the 2 events below the WIMP region are MSSI events. Above the ROI a total
of 25 events fall below the NR mean out of a total of 113,067 events (average
leakage of $2.2\times 10^{-4}$); some of these are also likely MSSI events
which survived the cuts developed for their removal.

For this reason, results of the fitting over the full range of $x$ are
presented in Table 2. Although the fits over the restricted domain better
replicated the behaviour of the leakage into the NR band, the fill fits may
capture the physics of the ER band more accurately, and may be useful for that
purpose.

Since discrimination is known to improve with decreasing energy in LXe (as
seen in Figure 1), it is important to consider the NR spectrum generated by
the neutron calibration when comparing with other experiments, in addition to
differences in detector parameters such as electric field and light
collection.

In a relatively large detector such as LUX, the LXe presents a thick target to
MeV neutrons. At the 2.45 MeV energy of the LUX D-D generator [26] the mean
elastic scattering length is 19 cm, and relatively few neutrons emerge from
the 50-cm diameter target without interacting elastically. In LUX, fewer than
$\sim$10% of elastic interactions are single scatters [27].

Figure 2: Geant4 simulation of the Am-Be calibration, showing the single-
scatter recoil spectrum in the fiducial volume. This corresponds to the
simulated spectrum in paper 1 but plotted here as a function of nuclear recoil
energy (no energy resolution applied). The WIMP ROI is indicated by the dashed
lines.

Contrast this with the ZEPLIN-III case. Here the neutron calibration was
conducted with the Am-Be source located immediately above the detector. The
mean elastic scattering length increases from $\sim$14 cm at 0.1–1 MeV neutron
energy, to over 30 cm above 5 MeV. Therefore, a 4-cm thick LXe disc presents
essentially as a thin target to the source. In this geometry, approximately
50% of the elastic interactions are single scatters, with a dominant component
scattering in the forward direction to produce low recoil energies — with
larger angle scatters more likely to multiple-scatter and be rejected. Figure
2 shows the simulated NR spectrum in ZEPLIN-III – essentially the same
spectrum as in paper 1. The NR spectrum in this thin detector has an enhanced
rate at lower energies ($\lesssim$20 keV) due to this effect, which should be
taken into account when comparing with other experiments.

## Acknowledgements

Credit for the data described in this note is due to the ZEPLIN-III
collaboration, which included Imperial College London (UK), the STFC
Rutherford Appleton Laboratory (UK), Edinburgh University (UK), ITEP-Moscow
(RU) and LIP-Coimbra (PT), working at the Boulby Underground Laboratory (UK).
I am particularly grateful to Matthew Szydagis (SUNY University at Albany) for
many discussions leading to his incorporating of this information into NEST,
and for his heroic efforts to develop an accurate LXe response model. Thanks
are also due to Vetri Velan (U.C. Berkeley) and to Ekaterina Kozlova (ITEP)
for applying the new NEST models to the ZEPLIN-III discrimination.

Table 1: ER and NR band data from the ZEPLIN-III First Science Run 2011 reanalysis, with the ER band fitted only for $x=\log_{10}(\mathrm{S2}/\mathrm{S1})\leq\mu_{ER}+\sigma_{ER}$. For each 1-keVee wide bin the nuclear recoil energy (NEST v2.0.1) and S1 photons detected are presented at the bin centre. The next set includes the number of ER counts in the bin ($N$), the observed leakage ($N_{O}$), the estimated leakage ($N_{E}$) and associated error ($\sigma_{E}$). Combined values for the whole ROI are presented in the last row. The ER band fit data include the four Skew-Gaussian parameters, as well as the mean and standard deviation ($\mu_{ER}$ and $\sigma_{ER}$). Corresponding parameters for the parameterisation of the Gaussian fits to the NR band are presented ($\mu_{NR}$ and $\sigma_{NR}$). S1 bins | ER counts & leakage |  ER band: fit for $-\infty<x\leq\mu_{ER}+\sigma_{ER}$ | NR band
---|---|---|---
keVee | keVnr | phd | $N$ | $N_{O}$ | $N_{E}$ | $\sigma_{E}$ | $A$ | $x_{0}$ | $\omega$ | $\alpha$ | $\mu_{ER}$ | $\sigma_{ER}$ | $\mu_{NR}$ | $\sigma_{NR}$
2–3 | 10.1 | 4.7 | 2,062 | 1 | 0.12 | 0.42 | 83.1 |  $+$0.021 | 0.159 | 1.14 |  $+$0.116 | 0.127 |  $-$0.333 | 0.155
3–4 | 12.9 | 6.6 | 2,371 | 0 | 0.09 | 0.31 | 107.9 |  $-$0.113 | 0.244 | 2.59 |  $+$0.069 | 0.163 |  $-$0.404 | 0.136
4–5 | 15.5 | 8.5 | 2,410 | 1 | 0.21 | 0.32 | 101.9 |  $-$0.160 | 0.210 | 1.99 |  $-$0.010 | 0.147 |  $-$0.457 | 0.123
5–6 | 17.9 | 10.4 | 2,472 | 0 | 0.29 | 0.54 | 101.3 |  $-$0.196 | 0.187 | 1.64 |  $-$0.069 | 0.137 |  $-$0.499 | 0.113
6–7 | 20.3 | 12.2 | 2,511 | 0 | 0.31 | 0.42 | 104.8 |  $-$0.242 | 0.208 | 1.94 |  $-$0.094 | 0.147 |  $-$0.534 | 0.106
7–8 | 22.6 | 14.1 | 2,634 | 1 | 0.24 | 0.34 | 109.9 |  $-$0.278 | 0.230 | 2.29 |  $-$0.110 | 0.157 |  $-$0.564 | 0.100
8–9 | 24.9 | 16.0 | 2,703 | 0 | 0.31 | 0.55 | 111.0 |  $-$0.287 | 0.203 | 1.82 |  $-$0.145 | 0.145 |  $-$0.590 | 0.095
9–10 | 27.1 | 17.9 | 2,668 | 0 | 0.28 | 0.37 | 113.9 |  $-$0.326 | 0.244 | 2.39 |  $-$0.146 | 0.165 |  $-$0.614 | 0.091
10–11 | 29.3 | 19.8 | 2,911 | 0 | 0.13 | 0.26 | 137.0 |  $-$0.360 | 0.316 | 3.52 |  $-$0.117 | 0.203 |  $-$0.635 | 0.087
11–12 | 31.3 | 21.6 | 3,046 | 1 | 0.20 | 0.32 | 137.8 |  $-$0.384 | 0.310 | 3.40 |  $-$0.147 | 0.199 |  $-$0.654 | 0.084
12–13 | 33.5 | 23.5 | 3,176 | 1 | 0.53 | 0.55 | 142.7 |  $-$0.380 | 0.303 | 2.82 |  $-$0.152 | 0.200 |  $-$0.671 | 0.081
13–14 | 35.6 | 25.4 | 3,075 | 0 | 1.10 | 2.25 | 151.3 |  $-$0.394 | 0.364 | 3.09 |  $-$0.117 | 0.237 |  $-$0.687 | 0.079
14–15 | 37.6 | 27.3 | 3,298 | 0 | 1.56 | 2.36 | 162.8 |  $-$0.370 | 0.292 | 2.09 |  $-$0.160 | 0.202 |  $-$0.702 | 0.076
15–16 | 39.7 | 29.2 | 3,540 | 0 | 1.35 | 3.17 | 167.0 |  $-$0.393 | 0.351 | 2.68 |  $-$0.131 | 0.233 |  $-$0.716 | 0.074
2–16 | 8.6–40.7 | 3.8–30.1 | 38,877 | 5 | 6.73 | 4.75 | – | – | – | – | – | – | – | –
Table 2: ER and NR band data as in Table 1, but with the ER band fitted over all values of $x=\log_{10}(\mathrm{S2}/\mathrm{S1})$. S1 bins | ER counts & leakage |  ER band: $-\infty<x<+\infty$ | NR band
---|---|---|---
keVee | keVnr | phd | $N$ | $N_{O}$ | $N_{E}$ | $\sigma_{E}$ | $A$ | $x_{0}$ | $\omega$ | $\alpha$ | $\mu_{ER}$ | $\sigma_{ER}$ | $\mu_{NR}$ | $\sigma_{NR}$
2–3 | 10.1 | 4.7 | 2,062 | 1 | 0.10 | 0.10 | 85.9 |  $+$0.007 | 0.178 | 1.47 |  $+$0.125 | 0.134 |  $-$0.333 | 0.155
3–4 | 12.9 | 6.6 | 2,371 | 0 | 0.22 | 0.31 | 98.9 |  $-$0.084 | 0.187 | 1.58 |  $+$0.042 | 0.138 |  $-$0.404 | 0.136
4–5 | 15.5 | 8.5 | 2,410 | 1 | 0.23 | 0.15 | 100.3 |  $-$0.156 | 0.201 | 1.85 |  $-$0.015 | 0.143 |  $-$0.457 | 0.123
5–6 | 17.9 | 10.4 | 2,472 | 0 | 0.22 | 0.18 | 102.9 |  $-$0.207 | 0.203 | 1.96 |  $-$0.063 | 0.143 |  $-$0.499 | 0.113
6–7 | 20.3 | 12.2 | 2,511 | 0 | 0.30 | 0.19 | 104.6 |  $-$0.243 | 0.209 | 1.97 |  $-$0.094 | 0.147 |  $-$0.534 | 0.106
7–8 | 22.6 | 14.1 | 2,634 | 1 | 0.33 | 0.28 | 109.8 |  $-$0.268 | 0.218 | 2.01 |  $-$0.113 | 0.152 |  $-$0.564 | 0.100
8–9 | 24.9 | 16.0 | 2,703 | 0 | 0.25 | 0.17 | 112.5 |  $-$0.294 | 0.215 | 2.04 |  $-$0.140 | 0.150 |  $-$0.590 | 0.095
9–10 | 27.1 | 17.9 | 2,668 | 0 | 0.32 | 0.20 | 111.0 |  $-$0.321 | 0.229 | 2.16 |  $-$0.154 | 0.158 |  $-$0.614 | 0.091
10–11 | 29.3 | 19.8 | 2,911 | 0 | 0.37 | 0.30 | 121.3 |  $-$0.332 | 0.236 | 2.14 |  $-$0.162 | 0.163 |  $-$0.635 | 0.087
11–12 | 31.3 | 21.6 | 3,046 | 1 | 0.46 | 0.36 | 126.9 |  $-$0.361 | 0.249 | 2.31 |  $-$0.179 | 0.170 |  $-$0.654 | 0.084
12–13 | 33.5 | 23.5 | 3,176 | 1 | 0.94 | 0.59 | 132.4 |  $-$0.355 | 0.245 | 1.94 |  $-$0.181 | 0.173 |  $-$0.671 | 0.081
13–14 | 35.6 | 25.4 | 3,075 | 0 | 3.15 | 3.75 | 128.2 |  $-$0.318 | 0.220 | 1.16 |  $-$0.186 | 0.175 |  $-$0.687 | 0.079
14–15 | 37.6 | 27.3 | 3,298 | 0 | 2.41 | 1.53 | 137.3 |  $-$0.338 | 0.244 | 1.44 |  $-$0.178 | 0.185 |  $-$0.702 | 0.076
15–16 | 39.7 | 29.2 | 3,540 | 0 | 2.99 | 3.01 | 147.6 |  $-$0.332 | 0.238 | 1.26 |  $-$0.183 | 0.185 |  $-$0.716 | 0.074
2–16 | 8.6–40.7 | 3.8–30.1 | 38,877 | 5 | 12.3 | 5.14 | – | – | – | – | – | – | – | –

## References

  * Lebedenko et al. [2009a] V. N. Lebedenko, et al. (ZEPLIN-III), Phys. Rev. D 80 (2009a) 052010\. doi:10.1103/PhysRevD.80.052010.
  * Lebedenko et al. [2009b] V. N. Lebedenko, et al. (ZEPLIN-III), Phys. Rev. Lett. 103 (2009b) 151302\. doi:10.1103/PhysRevLett.103.151302.
  * Akimov et al. [2010] D. Y. Akimov, et al. (ZEPLIN-III), Phys. Lett. B 692 (2010) 180–183. doi:10.1016/j.physletb.2010.07.042.
  * Akimov et al. [2012] D. Y. Akimov, et al. (ZEPLIN-III), Phys. Lett. B 709 (2012) 14–20. doi:10.1016/j.physletb.2012.01.064.
  * Chepel and Araújo [2013] V. Chepel, H. Araújo, JINST 8 (2013) R04001. doi:10.1088/1748-0221/8/04/R04001.
  * Szydagis et al. [2018] M. Szydagis, J. Balajthy, J. Brodsky, et al. (2018). doi:10.5281/zenodo.1314669.
  * Akerib et al. [2020] D. S. Akerib, et al. (LUX), arXiv (2020). arXiv:2004.06304.
  * Akerib et al. [2018] D. S. Akerib, et al., Phys. Rev. D 97 (2018) 102008. doi:10.1103/PhysRevD.97.102008.
  * Horn et al. [2011] M. Horn, et al. (ZEPLIN-III), Phys. Lett. B 705 (2011) 471--476. doi:10.1016/j.physletb.2011.10.038.
  * Solovov et al. [2012] V. N. Solovov, et al. (ZEPLIN-III), IEEE Trans. Nuc. Sci. 59 (2012) 3286--3293. doi:10.1109/TNS.2012.2221742.
  * Santos et al. [2011] E. Santos, et al. (ZEPLIN-III), JHEP 2011 (2011) 115\. doi:10.1007/JHEP12(2011)115.
  * Akimov et al. [2007] D. Y. Akimov, et al. (ZEPLIN-III), Astropart. Phys. 27 (2007) 46--60. doi:10.1016/j.astropartphys.2006.09.005.
  * Edwards et al. [2018] B. N. V. Edwards, et al., JINST 13 (2018) P01005. doi:10.1088/1748-0221/13/01/P01005.
  * Xu et al. [2019] J. Xu, et al., Phys. Rev. D 99 (2019) 103024. doi:10.1103/PhysRevD.99.103024.
  * Dahl [2009] C. E. Dahl, Ph.D. thesis, Princeton University, 2009.
  * Miller et al. [1968] L. S. Miller, S. Howe, W. E. Spear, Phys. Rep. 166 (1968) 871. doi:10.1103/PhysRev.166.871.
  * Benetti et al. [1993] P. Benetti, et al., Nucl. Instrum. Meth. A 329 (1993) 871. doi:10.1016/0168-9002(93)90954-G.
  * Albert et al. [2017] J. B. Albert, et al. (EXO-200), Phys. Rev. C 95 (2017) 025502\. doi:10.1103/PhysRevC.95.025502.
  * Faham et al. [2015] C. H. Faham, et al., JINST 10 (2015) P09010. doi:10.1088/1748-0221/2015/9/P09010.
  * López Paredes et al. [2018] B. López Paredes, et al., Astropart. Phys. 102 (2018) 56--66. doi:10.1016/j.astropartphys.2018.04.006.
  * Neves et al. [2010] F. Neves, et al. (ZEPLIN-III), Astropart. Phys. 33 (2010) 13--18. doi:10.1016/j.astropartphys.2009.10.004.
  * Fonseca et al. [2004] A. C. Fonseca, et al., in: IEEE Symp. Conf. Rec. Nuc. Sci. 2004., volume 1, pp. 572--576. doi:10.1109/NSSMIC.2004.1462260.
  * Gushchin et al. [1979] E. M. Gushchin, et al., Sov. Phys. JETP 49 (1979) 856.
  * Araújo et al. [2006] H. M. Araújo, et al. (ZEPLIN-III), Astropart. Phys. 26 (2006) 140--153. doi:10.1016/j.astropartphys.2006.05.006.
  * Araújo [2012] H. M. Araújo, Final Results from ZEPLIN-III at Boulby, https://events.pnnl.gov/jubilee/index.stm, 2012\. Presented at Dark Matter Silver Jubilee, Pacific Northwest National Laboratory, June 2012.
  * Akerib et al. [2016] D. S. Akerib, et al. (LUX), arXiv (2016). arXiv:1608.05381.
  * Akerib et al. [2015] D. S. Akerib, et al. (LUX), Astropart. Phys. 62 (2015) 33--46. doi:10.1016/j.astropartphys.2014.07.009.