MdB is supported by the Dutch Research Council (NWO) through Gravitation-grant
NETWORKS-024.002.003. Department of Mathematics and Computer Science, TU
Eindhoven, the<EMAIL_ADDRESS>Department of Mathematics and
Computer Science, TU Eindhoven, the<EMAIL_ADDRESS>Department
of Mathematics and Computer Science, TU Eindhoven, the
<EMAIL_ADDRESS>Mark de Berg and Morteza Monemizadeh and Yu
Zhong[100]Theory of computation Design and analysis of algorithms Petra
Mutzel, Rasmus Pagh, and Grzegorz Herman 3 29th Annual European Symposium on
Algorithms (ESA 2021) ESA 2021 ESA 2021 September 6–8, 2021 Lisbon, Portugal
204 13

#  $k$-Center Clustering with Outliers in the Sliding-Window Model

Mark de Berg  Morteza Monemizadeh  Yu Zhong

###### Abstract

The $k$-center problem for a point set $P$ asks for a collection of $k$
congruent balls (that is, balls of equal radius) that together cover all the
points in $P$ and whose radius is minimized. The $k$-center problem with
outliers is defined similarly, except that $z$ of the points in $P$ do need
not to be covered, for a given parameter $z$. We study the $k$-center problem
with outliers in data streams in the sliding-window model. In this model we
are given a possibly infinite stream $P=\langle
p_{1},p_{2},p_{3},\ldots\rangle$ of points and a time window of length $W$,
and we want to maintain a small sketch of the set $P(t)$ of points currently
in the window such that using the sketch we can approximately solve the
problem on $P(t)$.

We present the first algorithm for the $k$-center problem with outliers in the
sliding-window model. The algorithm works for the case where the points come
from a space of bounded doubling dimension and it maintains a set $S(t)$ such
that an optimal solution on $S(t)$ gives a $(1+\varepsilon)$-approximate
solution on $P(t)$. The algorithm is deterministic and uses
$O((kz/\varepsilon^{d})\log\sigma)$ storage, where $d$ is the doubling
dimension of the underlying space and $\sigma$ is the spread of the points in
the stream. Algorithms providing a $(1+\varepsilon)$-approximation were not
even known in the setting without outliers or in the insertion-only setting
with outliers. We also present a lower bound showing that any algorithm that
provides a $(1+\varepsilon)$-approximation must use
$\Omega((kz/\varepsilon)\log\sigma)$ storage.

###### keywords:

Streaming algorithms, $k$-center problem, sliding window, bounded doubling
dimension

##  1 Introduction

Clustering is one of the most important tools to analyze large data sets. A
well-known class of clustering algorithms is formed by centroid-based
algorithms, which include $k$-means clustering, $k$-median clustering and
$k$-center clustering. The latter type of clustering is the topic of our
paper. In the $k$-center problem one is given a set $P$ of points from a
metric space and a parameter $k$, and the goal is to find $k$ congruent balls
(that is, balls of equal radius) that together cover the points from $P$ and
whose radius is minimized. Note that the special case $k=1$ corresponds to the
minimum-enclosing ball problem. Data sets in practice often contain outliers,
leading to the _$k$ -center problem with outliers_. Here we are given, besides
$P$ and $k$, a parameter $z$ that indicates the allowed number of outliers.
Thus the radius of the balls in an optimal solution is given by

> $\mbox{{\sc opt}}_{k,z}(P)$ :=  the smallest radius $\rho$ such that we can
> cover all points from $P$, except for at most $z$ outliers, by $k$ balls of
> radius $\rho$.

In this paper we study the $k$-center problem with outliers in data streams,
where the input is a possibly infinite stream $P=\langle
p_{1},p_{2},\ldots\rangle$ of points. The goal is to maintain a solution to
the $k$-center problem as the points arrive over time, without any knowledge
of future arrivals and using limited (sub-linear) storage. Since we cannot
store all the points in the stream, we cannot expect to maintain an optimal
solution. Hence, the two main quality criteria of a streaming algorithm are
its approximation ratio and the amount of storage it uses. We will study this
problem in the _sliding-window model_. In this model we are given a window
length $W$ and we are, at any time $t$, only interested in the points that
arrived in the time window $(t-W,t]$. Working in the sliding-window model is
often significantly more difficult than working in the standard (insertion-
only) streaming model.

#### Previous work

Charikar et al.[DBLP:journals/siamcomp/CharikarCFM04] were the first to study
the metric $k$-center problem in data streams. They developed an algorithm in
the insertion-only model that computes an $8$-approximation for the $k$-center
problem using $\Theta(k)$ space. Later McCutchen and Khuller
[DBLP:conf/approx/McCutchenK08] improved the approximation ratio to
$2+\varepsilon$ at the cost of increasing the storage to
$O((k/\varepsilon)\log(1/\varepsilon))$. McCutchen and Khuller also studied
the $k$-center problem with $z\geqslant 1$ outliers, for which they gave a
$(4+\varepsilon)$-approximation algorithm that requires $O(kz/\varepsilon)$
space.

The above results are for general metric spaces. In spaces of _bounded
doubling dimension_ 111The _doubling dimension_ of a space $X$ is the smallest
number $d$ such that any ball $B$ in the space can be covered by $2^{d}$ balls
of radius $\operatorname{radius}(B)/2$. better bounds are possible. Indeed,
Ceccarello et al. [DBLP:journals/pvldb/CeccarelloPP19] gave a
$(3+\varepsilon)$-approximation algorithm for the $k$-center problem with $z$
outliers, thus improving the approximation ratio $(4+\varepsilon)$ for general
metrics. Their algorithm requires $O((k+z)(1/\varepsilon)^{d})$ storage, where
$d$ is the doubling dimension of the underlying space (which is assumed to be
a fixed constant).

The algorithms mentioned so far are deterministic. Charikar et al.
[DBLP:conf/stoc/CharikarOP03] and Ding et al. [DBLP:conf/esa/DingYW19] studied
sampling-based streaming algorithms for the Euclidean $k$-center problem with
outliers, showing that if one allows slightly more than $z$ outliers then
randomization can reduce the storage requirements. Our focus, however, is on
deterministic algorithms.

For the $k$-center problem in the sliding-window model, the only result we are
aware of is due to Cohen-Addad et al. [DBLP:conf/icalp/Cohen-AddadSS16]. They
deal with the $k$-center problem in general metric spaces, but without
outliers, and they propose a $(6+\varepsilon)$-approximation algorithm using
$O((k/\varepsilon)\log\sigma)$ storage, and a $(4+\varepsilon)$-approximation
for the special case $k=2$. Here $\sigma$ denotes (an upper bound on) the
spread of the points in the stream; in other words,
$\sigma:=\Delta_{\max}/\Delta_{\min}$, where $\Delta_{\max}$ is an upper bound
on the maximum distance and $\Delta_{\min}$ is a lower bound on the minimum
distance between any two distinct points. It is assumed that $\Delta_{\max}$
and $\Delta_{\min}$ are known to the algorithm. They also prove that any
algorithm for the $2$-center problem with outliers in general metric spaces
that achieves an approximation ratio of less than $4$ requires
$\Omega(W^{1/3})$ space, where $W$ is the size222Here the window size $W$ is
defined in terms of the number of points in the window, that is, the window
consists of the $W$ most recent points. We define the window in a slightly
more general manner, by defining $W$ to be the length (that is, duration) of
the window. Note that if we assume that the $i$-th point arrives at time
$t=i$, then the two models are the same. of the window. Table 1 gives an
overview of the known results on the $k$-center problem in the insertion-only
and the sliding-window model.

model | metric space | approx. | storage | outliers | ref.
---|---|---|---|---|---
insertion-only | general | $8$ | $k$ | no | [DBLP:journals/siamcomp/CharikarCFM04]
| general | $2+\varepsilon$ | $(k/\varepsilon)\log(1/\varepsilon)$ | no | [DBLP:conf/approx/McCutchenK08]
| general | $4+\varepsilon$ | $kz/\varepsilon$ | yes | [DBLP:conf/approx/McCutchenK08]
| bounded doubling | $3+\varepsilon$ | $(k+z)/\varepsilon^{d}$ | yes | [DBLP:journals/pvldb/CeccarelloPP19]
sliding window | general | $6+\varepsilon$ | $(k/\varepsilon)\log\sigma$ | no | [DBLP:conf/icalp/Cohen-AddadSS16]
| bounded doubling | $1+\varepsilon$ | $(kz/\varepsilon^{d})\log\sigma$ | yes | here
Table 1: Results for the $k$-center problem with and without outliers in the
insertion-only and the sliding-window model. Bounds on the storage are
asymptotic. In the papers where the metric space has bounded doubling
dimension or is Euclidean, the dimension $d$ is considered a constant.

While our main interest is in the $k$-center problem for $k>1$, our results
also apply when $k=1$. Hence, we also briefly discuss previous results for the
1-center problem.

For the 1-center problem in $d$-dimensional Euclidean space, streaming
algorithms that maintain an $\varepsilon$-kernel give a
$(1+\varepsilon)$-approximation. An example is the algorithm of Zarabi-Zadeh
[z-cpa-08] which maintains an $\varepsilon$-kernel of size
$O(1/\varepsilon^{(d-1)/2}\log(1/\varepsilon))$. Moreover, using only $O(d)$
storage one can obtain a 1.22-approximation for the 1-center problem without
outliers [DBLP:journals/algorithmica/AgarwalS15, cp-sdameb-14]. For the
1-center problem with outliers, one can obtain a
$(1+\varepsilon)$-approximation algorithm that uses $z/\varepsilon^{O(d)}$
storage by the technique of Agarwal et al. [DBLP:journals/dcg/AgarwalHY08].
Zarrabi-Zadeh and Mukhopadhyay [DBLP:conf/cccg/Zarrabi-ZadehM09] studied the
$1$-center problem with $z$ outliers in high-dimensional Euclidean spaces,
where $d$ is not considered constant, giving a $1.73$-approximation algorithm
that requires $O(d^{3}z)$ storage. Recently, Hatami anad Zarrabi-Zadeh
[DBLP:journals/comgeo/HatamiZ17] extended this result to $2$-center problem
with $z$ outliers, obtaining a $(1.8+\varepsilon)$-approximation using
$O(d^{3}z^{2}+dz^{4}/\varepsilon)$ storage. None of the 1-center algorithms
discussed above works in the sliding-window model.

A problem that is closely related to the 1-center problem is the _diameter
problem_ , where the goal is to maintain an approximation of the diameter of
the points in the stream. This problem has been studied in the sliding-window
model by Feigenbaum, Kannan, Zhang [DBLP:journals/algorithmica/FeigenbaumKZ04]
and later by Chan and Sadjad [cs-gosw-06], who gave a
$(1+\varepsilon)$-approximation for the diameter problem (without outliers) in
the sliding window model, using
$O((1/\varepsilon)^{(d+1)/2}\log(\sigma/\varepsilon))$ storage.

#### Our contribution

We present the first algorithm for the $k$-center problem with $z$ outliers in
the sliding-window model. It works in spaces of bounded doubling dimension and
yields a $(1+\varepsilon)$-approximation. So far a
$(1+\varepsilon)$-approximation was not even known for the $k$-center problem
without outliers in the insertion-only model. Our algorithm uses
$O((kz/\varepsilon^{d})\log\sigma)$ storage,333To correctly state the bound
for the case $z=0$ as well, we should actually write
$O((k(z+1)/\varepsilon^{d})\log\sigma)$. To keep the bound concise, we will
just write $O((kz/\varepsilon^{d})\log\sigma)$, however. where $d$ is the
doubling dimension and $\sigma$ is the spread, as defined above. Thus for the
1-center problem we obtain a solution that uses
$O((z/\varepsilon^{d})\log\sigma)$ storage. This solution also works for the
diameter problem. Note that also for the 1-center problem with outliers (and
the diameter problem with outliers) an algorithm for the sliding-window model
was not yet known. A useful property of the sketch444We use the word _sketch_
even though we do not study how to compose the sketches for two separate
streams into a sketch for the concatenation of the stream, as the term
_sketch_ seems more appropriate than _data structure_ , for example.
maintained by our algorithm for the $k$-center problem, is that it can also be
used for the $k^{\prime}$-center problem for any $k^{\prime}<k$, as well as
for the diameter problem. As in the previous papers on the $k$-center problem
(or the diameter problem) in the sliding-window model [cs-gosw-06,
DBLP:conf/icalp/Cohen-AddadSS16, DBLP:journals/algorithmica/FeigenbaumKZ04],
we assume that $\Delta_{\max}$ and $\Delta_{\min}$ (upper and lower bounds on
the maximum and minimum distance between any two points in the stream) are
known to the algorithm.

As mentioned above, our algorithm provides a $(1+\varepsilon)$-approximation.
More precisely, it maintains a set $S(t)\subset P(t)$ such that computing an
optimal solution for $S(t)$ and then suitably expanding the balls in the
solution, gives a $(1+\varepsilon)$-approximate solution for $P(t)$. Thus, to
obtain a $(1+\varepsilon)$-approximate solution for $P(t)$ one needs to
compute an optimal (or $(1+\varepsilon^{\prime})$-approximate, for a suitable
$\varepsilon^{\prime}$) solution for $S(t)$. Depending on the underlying space
this can be slow, and it may be preferable to compute, say, a 2-approximation
for $S(t)$, which would then give a $(2+\varepsilon)$-approximation for
$P(t)$. The various options in Euclidean spaces and general spaces of bounded
doubling dimension are discussed in Section 2.3.

Our second contribution is a lower bound for the $k$-center problem with
outliers in the sliding-window model. Our lower bound shows that any algorithm
that provides a $(1+\varepsilon)$-approximation must use
$\Omega((kz/\varepsilon)\log\sigma)$ storage. This matches our upper bound up
to the dependency on $\varepsilon$ and $d$. The lower-bound construction uses
points in $\mathbb{R}^{1}$, so it shows that our algorithm is optimal in this
case. The lower bound model is very general. It allows the algorithm to store
points, or weighted points, or balls, or whatever it wants so that it can
approximate an optimal solution for $P(t)$ at any time $t$. The main condition
is that each object comes with an expiration time which corresponds to the
expiration time of some point in the stream, and that the algorithm can only
change its state when an object expires or a new object arrives; see Section 3
for details.

##  2 The algorithm

Let $P:=\langle p_{1},p_{2},\ldots\rangle$ be a possibly infinite stream of
points from a metric space $X$ of doubling dimension $d$ and spread $\sigma$,
where $d$ is considered to be a fixed constant. We denote the arrival time of
a point $p_{i}$ by $\and(p_{i})$. We say that $p_{i}$ _expires_ at time
$t_{\mathrm{exp}}(p_{i}):=\and(p_{i})+W$, where $W$ is the given length of the
time window. To simplify the exposition, we assume that all arrival times and
departure times (that is, times at which a point expires) are distinct. For a
time $t$ we define $P(t)$ to be the set555We allow the same point from $X$ to
occur multiple times in the stream, so $P(t)$ is actually a multi-set.
Whenever we refer to “sets” in the remainder of the paper we mean “multi-
sets”. The distance $\Delta_{\min}$ is defined with respect to distinct
points, however. of points currently in the window. In other words,
$P(t):=\\{p_{i}:\and(p_{i})\leqslant t<t_{\mathrm{exp}}(p_{i})\\}$. For a
point $q\in X$ and a parameter $r\geqslant 0$, we use
$\operatorname{ball}(q,r)$ to denote the ball with center $q$ and radius $r$.

In the following we show how to maintain a sketch $\Gamma(t)$ of $P(t)$ for
the $k$-center problem with outliers. The idea behind our algorithm is as
follows. Consider an optimal solution for $P(t)$ consisting of $k$ balls
$B_{1},\ldots,B_{k}$ of radius $\rho_{\mathrm{opt}}$. Suppose we cover the
points in each ball $B_{i}$ by a number of smaller balls of radius
$\varepsilon\rho_{\mathrm{opt}}$; we will call these _mini-balls_. Since the
underlying space has doubling dimension $d$, we can do this using
$O(1/\varepsilon^{d})$ mini-balls for each ball $B_{i}$. To obtain a
$(1+\varepsilon)$-approximation, we do not need to know all the points: it
suffices to keep $z+1$ points in each mini-ball, since then we cannot
designate all points in the mini-ball as outliers. There are several
challenges to overcome to make this idea work. For instance, we do not know
$\rho_{\mathrm{opt}}$. Hence, we will develop an algorithm for the decision
version of the problem, which we will then apply “in parallel” to different
possible values for the optimal radius. But when $\rho$ is much smaller than
$\rho_{\mathrm{opt}}$ we have another challenge, namely that there can be many
outliers (which may need to be stored, because at some later moment in time
they may become inliers). Finally, since points arrive and expire, the balls
in an optimal solution move over time, which makes it hard to maintain the
mini-balls correctly. Below we show how to overcome these challenges.

###  2.1 A sketch for the decision problem

Recall that for a set $Q$ of points, $\mbox{{\sc opt}}_{k,z}(Q)$ denotes the
smallest radius $\rho$ such that we can cover all points from $Q$, except for
at most $z$ outliers, by $k$ balls of radius $\rho$, and that $\Delta_{\min}$
and $\Delta_{\max}$ are bounds on the minimum and maximum distance between any
two points in the stream. Let $\rho$ be a parameter with
$\Delta_{\min}\leqslant\rho\leqslant\Delta_{\max}$. We will design a sketch
$\Gamma(t)$ and a corresponding decision algorithm TryToCover with the
following properties:

  * •

The sketch $\Gamma(t)$ uses $O(kz/\varepsilon^{d})$ storage.

  * •

TryToCover either reports a collection $\mathcal{C}^{*}$ of $k$ balls of
radius $\mbox{{\sc opt}}_{k,z}(P(t))+2\varepsilon\rho$ that together cover all
points in $P(t)$ except for at most $z$ outliers, or it reports no. In latter
case we have $\mbox{{\sc opt}}_{k,z}(P(t))>2\rho$.

Our sketch $\Gamma(t)$ is a tuple
$[\tau(t),\mathcal{B}(t),\mathcal{R}(t)),P_{\mathrm{out}}(t)]$, where $\tau$
is a _timestamp_ , $\mathcal{B}(t)$ is a collection of mini-balls,
$\mathcal{R}(t)$ is a collection of so-called _representative sets_ , and
$P_{\mathrm{out}}(t)$ is a set of outliers. We will maintain the following
invariants.

(Inv-1)

For any time $t^{\prime}$ with $t\leqslant t^{\prime}<\tau(t)$ we are
guaranteed that $\mbox{{\sc opt}}_{k,z}(P(t^{\prime}))>2\rho$. The idea is
that when we find $k+z+1$ points with pairwise distances greater $2\rho$, then
we can set $\tau$ to the expiration time of the oldest of these points, and we
can delete this point (as well as any older points) from the sketch.

(Inv-2)

Each mini-ball $B\in\mathcal{B}(t)$ has radius $\varepsilon\rho$ and the
center of $B$, denoted by $\operatorname{center}(B)$, is a point from the
stream. Note that the center does not need to be a point from $P(t)$. The
mini-balls in $\mathcal{B}(t)$ are _well spread_ in the sense that no mini-
ball contains the center of any other mini-ball. In other words, we have
$\operatorname{dist}(\operatorname{center}(B),\operatorname{center}(B^{\prime}))>\varepsilon\rho$
for any two mini-balls $B,B^{\prime}\in\mathcal{B}(t)$.

(Inv-3)

For each mini-ball $B\in\mathcal{B}(t)$ the set $\mathcal{R}(t)$ contains a
_representative set_ $R(B)\subseteq B\cap P(t)$, and these are the only sets
in $\mathcal{R}(t)$. The representative sets $R(B)$ are pairwise disjoint, and
each set $R(B)$ contains at most $z+1$ points. When $|R(B)|=z+1$, we say that
the mini-ball $B$ is _full_.

(Inv-4)

Define $P_{\mathrm{in}}(t):=\bigcup_{B\in\mathcal{B}(t)}R(B)$ and let
$S(t):=P_{\mathrm{in}}(t)\cup P_{\mathrm{out}}(t)$ be the collection of all
points in our sketch. For any point $p_{i}\in P(t)\setminus S(t)$—these are
exactly the points that have not yet expired but that have been discarded by
the algorithm—we have (i) $t_{\mathrm{exp}}(p_{i})\leqslant\tau(t)$, and/or
(ii) $p_{i}\in B$ for a mini-ball $B\in\mathcal{B}(t)$ that is full and such
that all points in $R(B)$ arrived after $p_{i}$.

(Inv-5)

$|\mathcal{B}(t)|=O(k/\varepsilon^{d})$ and $|P_{\mathrm{out}}(t)|\leqslant
z$.

At time $t=0$, before the arrival of the first point, we have $\tau(t)=0$ and
$\mathcal{B}(t)=\mathcal{R}(t)=P_{\mathrm{out}}(t)=\emptyset$. Since
$P(0)=\emptyset$ this trivially satisfies the invariants. Before we prove that
we can maintain the sketch upon the arrival and departure of points, we
present our decision algorithm TryToCover and prove its correctness.

Algorithm 1 TryToCover$(\Gamma(t))$

1:$S(t)\leftarrow\bigcup_{B\in\mathcal{B}(t)}R(B)$

2:Compute $\mbox{{\sc opt}}_{k,z}(S(t))$ and the corresponding collection
$\mathcal{C}:=\\{C_{1},\ldots,C_{k}\\}$ of balls.

3:if $t<\tau(t)$ or $\mbox{{\sc opt}}_{k,z}(S(t))>2\rho$ then

4: Report no

5:else

6: Increase the radius of each ball $C_{i}\in\mathcal{C}$ by
$2\varepsilon\rho$.

7: Report the collection $\mathcal{C}^{*}:=\\{C^{*}_{1},\ldots,C^{*}_{k}\\}$
of expanded balls.

In line 2 we compute an optimal solution on the point set $S(t)$ How this can
be done depends on the underlying metric space and will be discussed in
Section 2.3. The following lemma establishes the correctness of the algorithm.

######  Lemma 2.1.

Algorithm TryToCover either reports a collection $\mathcal{C}^{*}$ of $k$
balls of radius $\mbox{{\sc opt}}_{k,z}(P(t))+2\varepsilon\rho$ that together
cover all points in $P(t)$ except for at most $z$ outliers, or it reports no.
In latter case we have $\mbox{{\sc opt}}_{k,z}(P(t))>2\rho$.

######  Proof 2.2.

First suppose the algorithm reports no. If this happens because $t<\tau(t)$
then $\mbox{{\sc opt}}_{k,z}(P(t))>2\rho$ by (Inv-1). Otherwise, this happens
because $\mbox{{\sc opt}}_{k,z}(S(t))>2\rho$. But then $\mbox{{\sc
opt}}_{k,z}(P(t))>2\rho$, because (Inv-3) implies that $S(t)\subseteq P(t)$.

Now suppose the algorithm reports a collection
$\mathcal{C}^{*}:=\\{C^{*}_{1},\ldots,C^{*}_{k}\\}$ of balls. Let
$\mathcal{C}$ be the corresponding set of balls before they were expanded.
Since $\mathcal{C}$ is an optimal solution for $S(t)$, the balls $C_{i}$ have
radius $\mbox{{\sc opt}}_{k,z}(S(t))\leqslant\mbox{{\sc opt}}_{k,z}(P(t))$ and
together they cover all points in $S(t)$ except for at most $z$ outliers. Now
consider a point $p_{i}\in P(t)\setminus S(t)$. To finish the proof, we must
show that $p_{i}$ is covered by one of the balls in $\mathcal{C}^{*}$. To this
end, first observe that $t_{\mathrm{exp}}(p_{i})>t$ because $p_{i}\in P(t)$.
Since TryToCover did not report no, this implies that
$t_{\mathrm{exp}}(p_{i})>\tau(t)$. Hence, we can conclude from (Inv-4) that
$p_{i}\in B$ for a mini-ball $B\in\mathcal{B}(t)$ that is full. Thus $R(B)$
contains $z+1$ points, and since we allow only $z$ outliers this implies that
at least one point from $R(B)$ is covered by a ball $C_{i}\in\mathcal{C}$.
Because $\operatorname{diam}(B)=2\varepsilon\rho$, this implies that $p_{i}$
must be covered by $C^{*}_{i}$, thus finishing the proof.

Next we show how to update the sketch $\Gamma(t)$.

#### Handling departures

When a point $p_{j}$ in one of our representative sets $R(B)$ expires, we
simply delete it from $R(B)$, and if $R(B)$ then becomes empty we remove
$R(B)$ from $\mathcal{R}(t)$ and $B$ from $\mathcal{B}(t)$. Similarly, if
$p_{j}$ was a point in $P_{\mathrm{out}}(t)$ we remove $p_{j}$ from
$P_{\mathrm{out}}(t)$.

It is trivial to verify that (Inv-1)–(Inv-3) and (Inv-5) still hold for the
updated sketch. To see that (Inv-4) holds as well, consider a point $p_{i}\in
P(t)\setminus S(t)$. The only reason for (Inv-4) to be violated, would be when
$p_{i}\in B$ for a mini-ball $B$ that was full before the deletion of $p_{j}$
but is no longer full after the deletion. However, (Inv-4) states that all
points in $R(B)$ arrived after $p_{i}$. Since $p_{i}$ did not yet expire, this
means that the point $p_{j}$ that currently expires cannot be a point from
$R(B)$.

#### Handling arrivals

The arrival of a point $p_{j}$ at time $t:=\and(p_{j})$ is handled by
Algorithm 2. We denote the sketch just before the arrival by $\Gamma(t^{-})$,
and the updated sketch by $\Gamma(t^{+})$.

Algorithm 2 HandleArrival$(\Gamma(t^{-}),p_{j})$

  1. 1.

If $p_{j}$ lies in an existing mini-ball $B\in\mathcal{B}(t^{-})$ then add
$p_{j}$ to $R(B)$. If $p_{j}$ did not lie in an existing mini-ball then add
$p_{j}$ to $P_{\mathrm{out}}(t^{-})$.

  2. 2.

Let $Q:=P_{\mathrm{out}}(t^{-})\cup\bigcup_{B\in\mathcal{B}(t^{-})}R(B)$ be
the set of all points in the current sketch, including the just inserted
point. Sort the points in $Q$ by decreasing arrival time, and let
$q_{1},q_{2}\ldots$ denote the sorted sequence of points—note that $q_{1}$ is
the newly inserted point $p_{j}$. Let $Q_{i}:=\\{q_{1},\ldots,q_{i}\\}$ denote
the set containing the first $i$ points from $Q$. Find the largest index
$i^{*}$ such that the following holds:

     * •

The 3-approximation algorithm of Charikar et al. [charikar2001algorithms] for
the $k$-center clustering algorithm with $z$ outliers, when run on
$Q_{i^{*}}$, reports a collection $\mathcal{B}^{*}$ of $k$ balls of radius at
most $6\rho$. (In fact, any other constant-factor approximation algorithm can
be used if we adjust the value $6\rho$ appropriately. For concreteness, we use
the one by Charikar et al.)

  3. 3.

If $Q_{i^{*}}\neq Q$ (and so the point $q_{i^{*}+1}$ exists) then set
$\tau(t^{+}):=\max(\tau(t^{-},t_{\mathrm{exp}}(q_{i^{*}+1}))$. Remove the
points in $Q\setminus Q_{i^{*}}$ from the representative sets they are in;
note that these points all have expiration time at least $\tau(t^{+})$.

  4. 4.

Let $\mathcal{B}^{*}:=\\{B_{1},\ldots,B_{k}\\}$ be the balls in the solution
reported for $Q_{i^{*}}$. Note that all points from $Q_{i^{*}}$, except for at
most $z$ outliers, lie in a ball from $\mathcal{B}^{*}$. The new set of mini-
balls and outliers is now computed as follows. Increase the radius of the
balls in $\mathcal{B}^{*}$ by $\varepsilon\rho$. Denote the set of expanded
balls by $\overline{\mathcal{B}}^{*}$

    1. (a)

Add each mini-ball $B\in\mathcal{B}(t^{-})$ whose center lies inside a ball
from $\overline{\mathcal{B}}^{*}$ to the set $\mathcal{B}(t^{+})$ and add
their representative sets to $\mathcal{R}(t^{+})$.

    2. (b)

Let $Z\subset Q_{i^{*}}$ be the set of points that are not in a representative
set added to $\mathcal{R}(t^{+})$ in Step 4a. Let $Z_{\mathrm{in}}\subseteq Z$
be the points that lie inside a ball from $\overline{\mathcal{B}}^{*}$. Go
over the points in $Z_{\mathrm{in}}$ one by one, in arbitrary order, and
handle each point $q$ as follows: If there is a mini-ball in the current set
$\mathcal{B}(t^{+})$ that contains $q$ then add $q$ to $R(B)$ for an arbitrary
such mini-ball $B$; otherwise create a mini-ball $B$ with center $q$ and
radius $\varepsilon\rho$, set $R(B):=\\{q\\}$ and add $B$ to
$\mathcal{B}(t^{+})$.

    3. (c)

For all mini-balls $B\in\mathcal{B}(t^{+})$ such that $|R(B)|>z+1$, remove the
oldest $|R(B)|-(z+1)$ points from $R(B)$.

    4. (d)

Set $P_{\mathrm{out}}(t^{+}):=Z\setminus Z_{\mathrm{in}}$. Note that these are
exactly the points from $Q_{i^{*}}$ that have not been added to a
representative set

######  Lemma 2.3.

After the arrival of point $p_{j}$ has been handled, the invariants
(Inv-1)–(Inv-5) are restored.

######  Proof 2.4.

(Inv-1)

If $\tau(t^{+})=\tau(t^{-})$ then obviously (Inv-1) still holds, so assume
that $\tau$ is updated by the algorithm in Step 3. Thus the algorithm of
Charikar et al. [charikar2001algorithms] returned a solution of radius more
than $6\rho$ on $Q_{i^{*}+1}$. Since the algorithm is a 3-approximation, this
means $\mbox{{\sc opt}}_{k,z}(Q_{i^{*}+1})>2\rho$. Because we sorted the
points on expiration time, we must have $\mbox{{\sc
opt}}_{k,z}(P(t^{\prime}))>2\rho$ for all $t^{\prime}$ with $t\leqslant
t^{\prime}<t_{\mathrm{exp}}(q_{i^{*}+1})$. Hence, (Inv-1) still holds.

(Inv-2)

By construction, the mini-balls in $\mathcal{B}(t^{+})$ have radius
$\varepsilon\rho$ and are centered at a point from the stream. The mini-balls
from $\mathcal{B}(t^{-})$ are well spread by induction, so we only need to
prove that any mini-balls created in Step 4b are well spread. This is true
because we only create a new mini-ball when its center does not lie inside an
existing mini-ball.

(Inv-3)

The representative sets $R(B)$ are disjoint by construction, and
$|R(B)|\leqslant z+1$ is guaranteed by Step 4c. Hence (Inv-3) holds.

(Inv-4)

Take a point $p_{i}\in P(t^{+})\setminus S(t^{+})$ and assume
$t_{\mathrm{exp}}(p_{i})>\tau(t^{+})$. We have two cases.

  * •

The first case is that $p_{i}$ was discarded due to the arrival of $p_{j}$.
Then it was either removed in Step 3, which implies
$t_{\mathrm{exp}}(p_{i})\geqslant\tau(t^{+})$; or it was removed in Step 4c,
which implies there is a full mini-ball $B\in\mathcal{B}(t^{+})$ such that all
points in $R(B)$ are newer than $p_{i}$. Hence, (Inv-4) holds for $p_{i}$

  * •

The second case is that $p_{i}$ was already discarded earlier. We can assume
that (Inv-4) holds before the arrival of $p_{j}$. If
$t_{\mathrm{exp}}(p_{i})\leqslant\tau(t^{-})$ then we also have
$t_{\mathrm{exp}}(p_{i})\leqslant\tau(t^{+})$ and we are done. So assume that
$p_{i}\in B$ for a mini-ball $B\in\mathcal{B}(t^{-})$ that was full and such
that all points in $R(B)$ arrived after $p_{i}$. If $R(B)$ contained a point
$p_{i^{\prime}}\in Q\setminus Q_{i^{*}}$ then
$t_{\mathrm{exp}}(p_{i})<t_{\mathrm{exp}}(p_{i^{\prime}})\leqslant\tau(t^{+})$,
and so (Inv-4) holds. If $R(B)$ only contained points from $Q_{i^{*}}$ then we
have two sub-cases.

The first sub-case is that $B$ is still present in $\mathcal{B}(t^{+})$. Then
$B$ must still be full, because $R(B)$ only contained points from $Q_{i^{*}}$.
Hence, (Inv-4) holds.

The second sub-case is that $B$ is not present in $\mathcal{B}(t^{+})$. Thus
its center must lie outside all balls in $\overline{\mathcal{B}}^{*}$. But
then the points in $R(B)$, which are all in $Q_{i^{*}}$, are outside any ball
in $\mathcal{B}^{*}$. But this is impossible, since $|R(B)|=z+1$ and
$\mathcal{B}^{*}$ has only $z$ outliers.

(Inv-5)

All mini-balls in $\mathcal{B}(t^{+})$ have their center inside one of the $k$
balls in $\overline{\mathcal{B}}^{*}$, which have radius at most $6\rho$.
Moreover, the mini-balls in $\mathcal{B}(t^{+})$ have radius $\varepsilon\rho$
and they are well spread. Since the underlying space has doubling dimension
$d$, this implies that $|\mathcal{B}(t^{+})|=O(k/\varepsilon^{d})$.

The outlier set $P_{\mathrm{out}}(t^{-})$ consists of the points from
$Q_{i^{*}}$ that lie outside the balls in $\overline{\mathcal{B}}^{*}$. Hence,
these points also lie outside the balls in $\mathcal{B}^{*}$. Since
$\mathcal{B}^{*}$ is a valid solution to the $k$-center problem with $z$
outliers, there are at most $z$ such points. Thus
$|P_{\mathrm{out}}(t^{+})|\leqslant z$.

###  2.2 A sketch for the optimization problem

Above we presented a sketch for a decision version of the problem, for given
parameters $\rho$ and $\varepsilon$. The sketch uses $O(kz/\varepsilon^{d})$
storage. We also gave an algorithmTryToCover that either reports a collection
$\mathcal{C}^{*}$ of $k$ balls of radius $\mbox{{\sc
opt}}_{k,z}(P(t))+2\varepsilon\rho$ covering all points in $P(t)$ except at
most $z$ outliers, or that reports no. In latter case we know that $\mbox{{\sc
opt}}_{k,z}(P(t))>2\rho$. To make the parameter $\rho$ and $\varepsilon$
explicit, we will from now on denote the sketch by
$\Gamma_{\rho,\varepsilon}$.

In the optimization version of the problem we wish to find $k$ congruent balls
of minimum radius that together cover all points in $P(t)$ except for at most
$z$ outliers. To obtain a $(1+\varepsilon)$-approximation for the optimization
problem, for a given $\varepsilon>0$, we maintain a sketch
$\Gamma_{\rho_{i},\varepsilon/2}$ for every $0\leqslant
i\leqslant\lfloor\log\sigma\rfloor$, where
$\rho_{i}:=2^{i}\cdot\Delta_{\min}$. We let
$\Gamma(t):=\\{\Gamma_{\rho_{0},\varepsilon/2},\ldots,\Gamma_{\rho_{\lfloor\log\sigma\rfloor},\varepsilon/2}\\}$
denote the collection of these sketches at time $t$. We can then obtain a
$(1+\varepsilon)$-approximate solution with the algorithm shown in Algorithm
3.

Algorithm 3 FindApproximateCenters$(\Gamma(t))$

1:$i\leftarrow 0$

2:repeat

3:
$\mathit{answer}\leftarrow\textsc{TryToCover}(\Gamma_{\rho_{i},\varepsilon/2})$;
$i\leftarrow i+1$

4:until $\mathit{answer}\neq$ no

5:if the radii of the balls in $\mathit{answer}$ is less than $\Delta_{\min}$
then

6: Reduce the radii of the balls to zero

7:Report $\mathit{answer}$

We obtain the following theorem. The theorem implicitly assumes that algorithm
tryToCover, which is called by FindApproximateCenters, has access to a
subroutine for computing an optimal solution. This issue will be further
discussed in Section 2.3.

######  Theorem 2.5.

The sketch $\Gamma(t)$ uses $O((kz/\varepsilon^{d})\log\sigma)$ storage, and
FindApproximateCenters$(\Gamma(t))$ reports a collection $\mathcal{C}^{*}$ of
balls of radius at most $(1+\varepsilon)\cdot\mbox{{\sc opt}}_{k,z}(P(t))$
covering all points from $P(t)$, except at most $z$ outliers.

######  Proof 2.6.

The storage bound follows immediately from the fact that each of the sketches
$\Gamma_{\rho_{i},\varepsilon/2}$ uses $O((kz/\varepsilon^{d}))$ storage. It
remains to prove the second part of the theorem.

First consider the case $\mbox{{\sc opt}}_{k,z}(P(t))=0$. When we run
$\textsc{TryToCover}(\Gamma_{\rho_{i},\varepsilon/2})$ with $i=0$, then by
Lemma 2.1 we will report a collection of balls of radius

$\mbox{{\sc
opt}}_{k,z}(P(t))+2(\varepsilon/2)\rho_{0}=\varepsilon\cdot\Delta_{\min}.$

Since $\varepsilon<1$, the radii are strictly smaller than $\Delta_{\min}$.
Since the balls are centered at points from $X$, we may as well reduce the
radii to zero, thus achieving an optimal solution.

Next, consider the case $\mbox{{\sc opt}}_{k,z}(P(t))>0$. Then $\mbox{{\sc
opt}}_{k,z}(P(t))\geqslant\Delta_{\min}=\rho_{0}$. Consider the loop in lines
2–4 and let $i^{*}$ be the value of the counter $i$ when we obtain
$\textsc{TryToCover}(\Gamma_{\rho_{i},\varepsilon/2})\neq$ no. Note that this
must happen at some point, because for $i=\lfloor\log\sigma\rfloor$ we have

$\rho_{i}=2^{\lfloor\log\sigma\rfloor}\cdot\Delta_{\min}\geqslant(\sigma/2)\cdot\Delta_{\min}=(1/2)\cdot\Delta_{\max}$

and so Lemma 2.1 guarantees that $\mathit{answer}\neq$ no. If $i^{*}=0$ then
the balls in the reported solution have radius

$\mbox{{\sc
opt}}_{k,z}(P(t))+2(\varepsilon/2)\rho_{0}\leqslant(1+\varepsilon)\cdot\mbox{{\sc
opt}}_{k,z}(P(t)).$

Otherwise we know that the answer for $i=i^{*}-1$ is no, which implies that
$\mbox{{\sc opt}}_{k,z}(P(t))>2\rho_{i^{*}-1}=\rho_{i^{*}}$. Hence, the balls
in the solution that is reported for $i^{*}$ have radius

$\mbox{{\sc
opt}}_{k,z}(P(t))+2(\varepsilon/2)\rho_{i^{*}}\leqslant(1+\varepsilon)\cdot\mbox{{\sc
opt}}_{k,z}(P(t)).$

Our sketch for the $k$-center problem can also be used for the
$k^{\prime}$-center problem for $k^{\prime}<k$. Moreover, a sketch for the
$k$-center problem for $k\geqslant 1$ can be used for the diameter problem.
Recall that the diameter problem with outliers for the set $P(t)$ asks for the
value

$\operatorname{diam}_{z}(P(t)):=\min\\{\operatorname{diam}(P(t)\setminus
Q):|Q|=z\\},$

that is, $\operatorname{diam}_{z}(P(t))$ is the smallest diameter one can
obtain by deleting $z$ outliers from $P(t)$. We say that an algorithm reports
a $(1-\varepsilon)$-approximation to $\operatorname{diam}_{z}(P(t))$ if it
reports a value $D$ with
$(1-\varepsilon)\cdot\operatorname{diam}_{z}(P(t))\leqslant
D\leqslant\operatorname{diam}_{z}(P(t))$.

######  Theorem 2.7.

The sketch for the $k$-center problem with outliers as presented above can
also be used to provide a $(1+\varepsilon)$-approximation for the
$k^{\prime}$-center problem with outliers, for any $1\leqslant
k^{\prime}\leqslant k$. Moreover, it can be used to provide a
$(1-2\varepsilon)$-approximation for the diameter problem with outliers.

######  Proof 2.8.

The value $k$ plays a role in (Inv-1) and (Inv-5), not in the other
invariants. In (Inv-5) the value of $k$ determines the size of
$\mathcal{B}(t)$—it has no influence on the correctness. As for (Inv-1), we
observe that $\mbox{{\sc opt}}_{k^{\prime},z}(P(t))\geqslant\mbox{{\sc
opt}}_{k,z}(P(t))$ for any $k^{\prime}\leqslant k$, so the fact that (Inv-1)
holds for $k$ implies that it holds for $k^{\prime}<k$ as well. Hence, a
sketch for the $k$-center problem will have the properties required of a
sketch for the $k^{\prime}$-center problem (except that the storage depends on
$k$ instead of $k^{\prime}$.) Thus running TryToCover on a sketch for the
$k$-center, where in line 2 we compute $\mbox{{\sc
opt}}_{k^{\prime},z}(P(t))$, will give a correct result for $k^{\prime}$.

Now consider the diameter problem. Suppose we run TryToCover on a sketch for
the $k$-center problem, where in line 2 we compute
$\operatorname{diam}_{z}(P(t))$, and instead of lines 6–7 we report
$D:=\operatorname{diam}_{z}(S(t))$. We claim that if the algorithm reports no
then we have $\operatorname{diam}_{z}(P(t))>2\rho$, and otherwise
$\operatorname{diam}_{z}(P(t))-4\varepsilon\rho\leqslant
D\leqslant\operatorname{diam}_{z}(P(t))$.

Note that $\operatorname{diam}_{z}(P(t))\geqslant\mbox{{\sc opt}}_{k,z}(P(t))$
for any $k\geqslant 1$. Hence, when $t<\tau(t)$ then we have
$\operatorname{diam}_{z}(P(t))\geqslant\mbox{{\sc opt}}_{k,z}(P(t))>2\rho$.
This implies that the claim holds when TryToCover reports no.

If TryToCover does not report no, it reports
$D:=\operatorname{diam}_{z}(S(t))$. Clearly we then have
$D\leqslant\operatorname{diam}_{z}(P(t))$. Now suppose for a contradiction
that $D<\operatorname{diam}_{z}(P(t))-4\varepsilon\rho$. Let $p_{i},p_{j}\in
P(t)$ be such that
$\operatorname{dist}(p_{i},p_{j})=\operatorname{diam}_{z}(P(t))$. We will
argue that there are points $p_{i^{\prime}},p_{j^{\prime}}\in S(t)$ such that
$\operatorname{dist}(p_{i},p_{i^{\prime}})\leqslant 2\varepsilon\rho$ and
$\operatorname{dist}(p_{j},p_{j^{\prime}})\leqslant 2\varepsilon\rho$. But
then we would have
$D=\operatorname{diam}_{z}(S(t))\geqslant\operatorname{diam}_{z}(P(t))-4\varepsilon\rho$,
which contradicts the assumption. We will argue the existence of
$p_{i^{\prime}}$; the argument for $p_{j^{\prime}}$ is similar. If $p_{i}\in
S(t)$ then we can take $p_{i^{\prime}}:=p_{i}$ and we are done. Otherwise, as
argued in the proof of Lemma 2.1, we know that $p_{i}\in B$ for a ball $B\in
B(t)$ that is full. In particular $R(B)$ contains at least one point
$p_{i^{\prime}}$, and this point must be at distance at most
$2\varepsilon\rho$ from $p_{i}$, as claimed.

We have proved the claim that if the algorithm reports no then we have
$\operatorname{diam}_{z}(P(t))>2\rho$, and otherwise we have
$\operatorname{diam}_{z}(P(t))-4\varepsilon\rho\leqslant
D\leqslant\operatorname{diam}_{z}(P(t))$. Plugging this claim for the decision
problem into the mechanism to obtain a sketch for the optimization
problem—recall that there we used $\varepsilon/2$ as parameter—now gives the
desired result.

Theorem 2.7 implies that there exists a sketch for the diameter problem with
outliers in the sliding-window model that gives a
$(1+\varepsilon)$-approximation to $\operatorname{diam}_{z}(P(t))$ using
$O((z/\varepsilon^{d})\log\sigma)$ storage, namely the sketch for the 1-center
problem.

###  2.3 Time complexity

Above we focused on the storage used by our sketch, and on the approximation
ratio it can potentially provide. We now discuss the time complexity.

The algorithm that handles departures trivially runs in $O(1)$ time. The most
time-consuming step in the algorithm that handles arrivals is Step 2, where we
run the algorithm of Charikar et al. [charikar2001algorithms] on a set of
$O(kz/\varepsilon^{d})$ points. This takes $O((kz/\varepsilon^{d})^{3})$ time.
Note that, both for departures and arrivals, we need to execute the respective
algorithms for each of the $\log\sigma$ sketches
$\Gamma_{\rho_{i},\varepsilon/2}$ we maintain.

The time needed for FindApproximateCenters is more interesting, since it calls
TryToCover, which is supposed to compute an optimal solution for the
$k$-center problem with outliers on a given set $S(t)$ of $O(kz/\varepsilon)$
points. It is routine to check that if TryToCover would use a $c$-approximate
solution on $S(t)$, instead of an optimal solution, our final result would be
a $c(1+\varepsilon)$-approximation. In $d$-dimensional Euclidean space we can
solve the $k$-center problem with outliers in time polynomial in $n:=|S(t)|$
(for constant $k$ and $d$), as follows: first generate all $O(n^{d+1})$
potential centers—there are $O(n^{d+1})$ potential centers because the
smallest enclosing ball of a given point set is defined by at most $d+1$
points—then generate all possible collections of $k$ such centers, and then
for each of the $O(n^{(d+1)k})$ such collections find the minimum radius
$\rho$ such that we can cover all except for $z$ points. A similar approach is
possible for other metrics in $\mathbb{R}^{d}$ that are sufficiently well-
behaved (such as $\ell_{p}$ metrics, for instance).

For arbitrary metric spaces the situation is more tricky. The standard
assumption, which we also make, is that we can compute the distance between
any two given points from the metric space in $O(1)$ time. Still, computing an
optimal solution on the set $S(t)$ can be quite slow or perhaps even
infeasible. For example, when an optimal center is a point from the metric
space that does not occur in the stream, then the algorithm may be unable to
retrieve this center. So unless we are in Euclidean space, or some other
“well-defined” space, it seems most natural to define the underlying space as
consisting of exactly the points in the stream. Note that this can still be
somewhat problematic, as it may require the algorithm to use points that have
already expired as centers for the current set $S(t)$. These issues seem
unavoidable for any algorithm that maintains a sketch in the sliding-window
model. Also note that, using just the points in the current set $P(t)$ as
centers, one can always obtain a 2-approximation to the optimal clustering.
Invariant (Inv-4) thus implies that by using the set $S(t)$ as potential
centers we can obtain a $(2+\varepsilon)$ approximation. Also note that the
optimal $k$-center clustering with $z$ outliers on $S(t)$, under the
restriction that the centers come from $S(t)$, can be trivially computed in
$O(|S(t)|^{k+2})$ time.

The following theorem summarizes the performance of our sketch.

######  Theorem 2.9.

Consider the $k$-center problem with $z$ outliers in the sliding-window model,
for streams of points from a space with doubling dimension $d$. Let
$\Delta_{\min}$ and $\Delta_{\max}$ be given (lower and upper) bounds on the
minimum and maximum distance between any two points in the stream, and let
$\sigma:=\Delta_{\max}/\Delta_{\min}$ be (an upper bound on) the spread of the
stream. Suppose we have a $c$-approximation algorithm for the static version
of the problem that runs in $T_{k,z}(n)$ time on a set of $n$ points. Then for
any $0<\varepsilon<1$ we can maintain a sketch with the following properties:

  * •

The sketch uses $O((kz/\varepsilon^{d})\log\sigma)$ storage.

  * •

Departures and arrivals can be handled in $O(\log\sigma)$ and
$O((kz/\varepsilon^{d})^{3}\log\sigma)$ time, respectively.

  * •

At any time $t$, the algorithm can report a valid solution for $P(t)$ of cost
at most $(1+\varepsilon)c\cdot\mbox{{\sc opt}}_{k,z}(P(t))$. The time needed
to compute the solution is $T_{k,z}(n)$, where $n:=O(kz/\varepsilon^{d})$.

##  3 A lower bound

Above we presented a sketch of size $O((kz/\varepsilon^{d})\log\sigma)$ that
provides a $(1+\varepsilon)$-approximation for the $k$-center problem with $z$
outliers in the sliding-window model. In this section we show that this is
tight, up to the dependency on $d$. We will first show that to obtain any
constant approximation ratio for the problem in $\mathbb{R}^{1}$, a sketch
must use $\Omega(kz)$ storage. Then we prove that, for $0<\varepsilon<1$, any
sketch giving a $(1+\varepsilon)$-approximation in $\mathbb{R}^{1}$ must use
$\Omega((kz/\varepsilon)\log\sigma)$ storage.

#### The lower-bound model

Our lower-bound model is extremely simple and general. We allow the algorithm
to store points, or weighted points, or balls, or whatever it wants so that it
can approximate an optimal solution for $P(t)$ at any time $t$. We only make
the following assumptions. Let $S(t)$ be the collection of objects being
stored at time $t$.

  * •

Each object in $S(t)$ is accompanied by an expiration time, which is equal to
the expiration time of some point $p_{i}\in P(t)$.

  * •

Let $p_{i}\in P(t)$. If no object in $S(t)$ uses $t_{\mathrm{exp}}(p_{i})$ as
its expiration time, then no object in $S(t^{\prime})$ with $t^{\prime}>t$ can
use $t_{\mathrm{exp}}(p_{i})$ as its expiration time. (Once an expiration time
has been discarded, it cannot be recovered.)

  * •

The solution reported by the algorithm is uniquely determined by $S(t)$, and
the algorithm only modifies $S(t)$ when a new point arrives or when an object
in $S(t)$ expires.

  * •

The algorithm is deterministic and oblivious of future arrivals. In other
words, the set $S(t)$ is uniquely determined by the sequence of arrivals up to
time $t$, and the solution reported for $P(t)$ is uniquely determined by
$S(t)$.

The storage used by the algorithm is defined as the number of objects in
$S(t)$. The algorithm can decide which objects to keep in $S(t)$ anyway it
wants; it may even keep an unbounded amount of extra information in order to
make its decisions. The algorithm can also derive a solution for $P(t)$ in any
way it wants, as long as the solution is valid and uniquely determined by
$S(t)$. Clearly, the sketch from the previous section adheres to the model.

#### A lower bound for constant-factor approximations

Next we give a simple example showing that any constant-factor approximation
must use $\Omega(kz)$ storage.

Let

######  Algorithm 1.

be an algorithm that maintains a $c$-approximation for the problem in
$\mathbb{R}^{1}$. Consider the set $P(t)$ shown in Figure 1. The set $P(t)$
consists of $k+1$ clusters $C_{1},\ldots,C_{k+1}$ of $z+1$ points each. The
points within a cluster are at distance 1 from each other (so the radius of a
cluster is $z/2$) and the distance between two consecutive clusters is $cz+1$.
Note that the spread of the set is $(k+1)z+k(cz+1)=\Theta(ckz)$.

Figure 1: The lower-bound construction showing that any $c$-approximation
algorithm must use $\Omega(kz)$ storage.

Let $T_{\mathrm{exp}}$ be the set of expiration times of the points in $P(t)$,
except for the first point. Note that $|T_{\mathrm{exp}}|=(k+1)(z+1)-1$.
Suppose at least one of these expiration times, say the expiration time of
point $p^{*}$, is not used by any of the objects in $S(t)$. The adversary now
proceeds as follows. Let $Q\subset P(t)$ be the set of points expiring before
$t_{p^{*}}$, where $t_{p^{*}}:=t_{\mathrm{exp}}(p^{*})$ is the expiration time
of $p^{*}$. Whenever a point in $Q$ expires, the adversary immediately
replaces it by a point at the same location.

Now let $t_{p^{*}}^{-}$ and $t_{p^{*}}^{+}$ be the times immediately before
and after $t_{p^{*}}$, respectively. Then at time $t_{p^{*}}^{-}$ we have the
point set shown in Figure 1, while at time $t_{p^{*}}^{+}$ the point $p^{*}$
has expired. Since we are allowed to use only $k$ balls and $z$ outliers, any
valid solution at time $t_{p^{*}}^{-}$ must have a ball that contains points
from at least two of the clusters. Since the distance between any two clusters
is at least $cz+1$, the radius of such a ball is at least $(cz+1)/2$. Hence,
$\mbox{{\sc opt}}_{k,z}(P(t_{p^{*}}^{-}))\geqslant(cz+1)/2$. On the other
hand, at time $t_{p^{*}}^{+}$ there is a cluster $C_{i^{*}}$ of size $z$. Thus