# Online $k$-Median with Consistent Clusters111Moseley and Newman are
supported in part by a Google Research Award, an Inform Research Award, a
Carnegie Bosch Junior Faculty Chair, and NSF grants CCF-2121744 and
CCF-1845146. Pruhs is supported in part by NSF grants CCF-1907673,
CCF-2036077, CCF-2209654 and an IBM Faculty Award.

Benjamin Moseley Tepper School of Business. Carnegie Mellon University.
Heather Newman Department of Mathematical Sciences. Carnegie Mellon
University. Kirk Pruhs Computer Science Department. University of Pittsburgh.

###### Abstract

We consider the online $k$-median clustering problem in which $n$ points
arrive online and must be irrevocably assigned to a cluster on arrival. As
there are lower bound instances that show that an online algorithm cannot
achieve a competitive ratio that is a function of $n$ and $k$, we consider a
beyond worst-case analysis model in which the algorithm is provided a priori
with a predicted budget $B$ that upper bounds the optimal objective value. We
give an algorithm that achieves a competitive ratio that is exponential in the
the number $k$ of clusters, and show that the competitive ratio of every
algorithm must be linear in $k$. To the best of our knowledge this is the
first investigation in the literature that considers cluster consistency using
competitive analysis.

##  1 Introduction

Clustering problems, such as $k$-means clustering and $k$-median clustering,
are a classic genre of learning / data mining problems [2]. Typically the
input consists of a collection $X=\\{x_{1},\ldots,x_{n}\\}$ of points in some
metric space $\mathcal{M}$ (typically $\Re^{d}$ with the 1-norm or 2-norm) and
a positive integer $k$. The output for a center-based clustering problem is a
collection $c_{1},\ldots,c_{k}$ of $k$ points from $X$, called centers, that
succinctly summarize the data points. The implicit cluster $C_{i}$
corresponding to the center $c_{i}$ is the collection of points in $X$ whose
closest center is $c_{i}$, that is
$C_{i}=\\{x_{j}\mid\operatorname*{arg\,min}_{h\in[k]}d(x_{j},c_{h})=i\\}$,
where $d(\cdot,\cdot)$ is the distance function for the metric space. The
output for a cluster-based clustering problem is a partition $C_{1},\ldots
C_{k}$ of $X$ into $k$ parts, called clusters. The implicit center of each
cluster $C_{i}$ is then $c_{i}=\operatorname*{arg\,min}_{x_{h}\in
C_{i}}\sum_{x_{j}\in C_{i}}d(x_{h},x_{j})$. For both center-based clustering
and cluster-based clustering, the objective is to minimize the cost of the
clustering. This paper considers the $k$-median objective which is the
aggregate distance from each point to the center of its cluster, that is
$\sum_{i=1}^{k}\sum_{x_{j}\in C_{i}}d(x_{j},c_{i})$.

Here we consider applications where the data points in $X$ arrive online over
time. In a center-based clustering problem, the online algorithm maintains a
collection of centers. In a cluster-based problem, the online algorithm needs
to assign the data points to a cluster when they arrive, that is each point
$x_{j}$ needs to be assigned a label $\ell_{j}\in[k]$ when $x_{j}$ arrives.

An application of online clustering given by [14] is the task of clustering
news articles that arrive online. For example at Yahoo news or Google news. We
will refer to these outlets as the news providers. The news provider selects
some (approximately) fixed number $k$ of articles to feature on the news
homepage, and has a “view complete coverage” link next to each article to see
all the news stories on this topic. The problem of selecting the best $k$
articles that summarize all current news articles is better modeled as a
center-based clustering. The problem of partitioning all news articles into
clusters of similar articles is better modeled as a cluster-based clustering.
Other applications can be found in [13, 11], but we will use the news story
clustering application as our running canonical example.

A line of research [9, 8, 11, 13] within online clustering goes by moniker of
consistent clustering. Research on consistent clustering studies the trade-
offs and relationship between the following objectives:

  * •

Maximizing the Quality of the Clustering: One seeks the cost of the clustering
to be small. The most common metric to measure the quality of a solution is
the ratio of the cost of this solution to cost of the optimal solution. The
most common metric to measure the quality of an online algorithm is the
competitive ratio, which is the maximum (over all inputs) of the ratio of the
cost of the online algorithm’s solution to the optimal cost.

  * •

Maximizing Consistency: Ideally one would like the centers in a center-based
problem, or the clusters in a cluster-based problem, to be consistent over
time. That is, they should change as little as possible. So for example, the
news provider doesn’t want the clusters to completely change every time a new
news article is written.

###  1.1 Prior Work on Consistent Clustering

$k$-median clustering is NP-hard, but constant factor approximation
polynomial-time algorithms are known [5, 10, 1, 12, 3].

All prior algorithmic research on consistent clustering that we are aware of
[9, 8, 11, 13] is center-based. That is, the online algorithm explicitly
maintains a collection of centers, and the clustering is implicit. That is,
each point is assumed to be associated with the closest center, but there are
no restrictions on how often points’ associated centers can change.

The first paper [13] in this line of research gave a lower bound that showed
that one can not simultaneously have both high quality and maximum
consistency. That is, they showed that if a center cannot be changed once it
is established, then there is no algorithm whose competitive ratio can be
bounded by any function of $n$ and $k$.

Thus various “beyond worst-case analysis” (see [17]) approaches have been used
in the literature to attempt to circumvent the obstacle presented by this
lower bound. One approach is to use bi-criteria analysis or _resource
augmentation_ analysis. This analysis allows the online algorithm to use more
than $k$ centers, and then compares the cost of the algorithm’s clustering to
the optimal one using $k$ centers [13]. A second approach is to allow the
algorithm _recourse_ , which in this setting means allowing the algorithm to
change the centers (or clusters) a small number of times [11, 8, 9]. Another
approach is to consider learning augmented algorithms, which assumes that the
algorithm receives some advice/information a priori about the input. For
example, in the news application, the news provider presumably has prior data
that it could use to predict with some reasonable accuracy some properties of
the input.

[13] gives a randomized algorithm for $k$-means clustering and analyzes this
algorithm using _resource augmentation_ analysis. [13] shows that the expected
number of clusters/centers used by their algorithm is $O(k\log n\log n\Delta)$
and at all times the expected cost of the clustering using these centers is at
most $O(\log n)$ times the optimal cost using $k$ clusters. Here $\Delta$ is
the aspect ratio of the data points, which is the ratio between the distance
between the furthest pair of points and the distance between the closest pair
of points. The algorithm leverages a randomized online algorithm for facility
location from [15] to decide whether to create a new center at a newly
arriving data point. Once a center is established, it is maintained throughout
the course of the algorithm. Finally, [13] gives a randomized algorithm that
requires a priori knowledge of $n$ and a lower bound of the optimal with $k$
centers, and that maintains a collection of $O(k\log n\log\alpha)$ centers in
expectation that has expected cost $O(1)$ times the optimal cost with $k$
centers. Here $\alpha$ is the ratio between actual optimal cost with $k$
centers and the lower bound provided a priori to the algorithm.

[11] give a randomized algorithm for $k$-means or $k$-median clustering that
uses _recourse_. The algorithm maintains the invariant that the cost of the
current centers is always $O(1)$-competitive with the optimal clustering of
the data points seen to date. To maintain this invariant, the expected number
of cluster center changes used by the algorithm is $O(k^{2}\log^{4}n\Delta)$.
[11] show a similar lower bound, that is they show that every algorithm
requires $\Omega(k\log_{c}\frac{\Delta}{k})$ center changes to maintain
$O(c)$-competitiveness. Further, [11] show that it possible to maintain
$O(1)$-competitiveness with $O(k\log^{2}n\Delta)$ center changes, but this is
just an existential result, and no algorithm to achieve this was given. In
followup paper [8] gave a randomized algorithm that maintains
$O(1)$-competitiveness with $O(k\operatorname{polylog}(n\Delta)$ cluster
changes. The results in [11] were extended to $k$-median clustering with
outliers (so one could opt to not cluster a pre-specified number of points) in
[9]. [11] also observes that for $k$-center clustering an algorithm from [6]
can be used to maintain an $O(1)$-competitive clustering with $O(k\log
n\Delta)$ center changes.

While not directly germane for the work in this paper, there is also research
on online clustering in the streaming setting, where the emphasis is more on
the algorithm using a small amount of memory, or quickly responding to the
arrival of a new data point (e.g. [4, 7]).

###  1.2 Our Contribution

Our initial research goal was to investigate consistent clustering for
cluster-based problems (recall that all the past algorithmic consistent
clustering publications that we are aware of focus on center-based
clustering). We are interested in applications where the focus is on
explicitly maintaining consistent clusters (and not necessarily on maintaining
consistent centers). The application where Google or Yahoo news is trying to
maintain collections of similar news articles is an example of such an
application. Note that even the algorithms from [13] that are perfectly
consistent from a center perspective, in that once a center is established it
persists until the end of the algorithm, are not necessarily consistent from a
cluster perspective in that a data point could change clusters every time a
new center is established. All one can say (at least naively) about the
cluster consistency of the algorithms from [13] is that no data point changes
clusters more than $O(k\log n\log n\Delta)$ times.

Specifically, our research goal is to determine whether some reasonable
competitiveness with respect to cost can be achieved if each data point has to
be irrevocably assigned a cluster, or equivalently a label, when it arrives.

The lower bound from [13] implies that we will need to take some beyond worst-
case analysis approach as otherwise there is no algorithm with bounded
approximation ratio. For reasons we explain in Section 2, we will take a
learning augmented algorithms approach, and assume that the algorithm is
provided a priori with an estimated upper bound $B$ of the cost of the final
optimal clustering. Our algorithms will then try maintain a clustering of low
cost relative to $B$, not the current optimal cost for the points that have
arrived to date. Thus we will say an algorithm is $c$-competitive with respect
to the budget if the algorithms cost is at most $c\cdot B$ on instances where
the optimal cost is at most $B$ (after all points arrive).

We develop a lower bound in Section B that the competitiveness of any
algorithm relative to the budget must be $\Omega(k)$. In light of this
observation, a natural question is whether one can find an algorithm whose
competitiveness with respect to the budget is $O(f(k))$ for some function $f$,
that depends only on the number of centers $k$, and not on the number of
points $n$. Such an algorithm is constant competitive when $k$ is fixed. We
answer this in the affirmative by giving a (polynomial-time deterministic)
online algorithm that is $O(k^{5}3^{k})$-competitive with respect to the
budget. Thus, we know the competitive ratio must depend on $k$ by the lower
bound and we give an upper-bound that only depends on $k$. Note that in most
clustering applications while the number of points $n$ to be clustered may be
large, the number $k$ of clusters is typically a modestly small constant, say
10 for example [2].

##  2 Technical Overview

To understand the motivation for learning-augmented approach, let us consider
the lower bound instance from [13]. It is sufficient to assume $k=2$. The
first point $x_{1}$ arrives and is assigned some irrevocable label. Then
assume the second data point $x_{2}$ arrives a unit distance from $x_{1}$. If
the online algorithm assigns $x_{2}$ the same label as $x_{1}$ then the cost
of the algorithm’s clustering is 1, and the optimal cost is 0 (which is the
cost if each of these data points were given a different labels). This results
in the algorithm having in unbounded competitiveness. In contrast, if the
algorithm gave $x_{2}$ the a different label as $x_{1}$ then the third data
point $x_{3}$ could arrive very far away. In which case, the algorithm’s
clustering would necessarily have very high cost (as $x_{3}$’s label would
have to be either the same as $x_{1}$’s or the same as $x_{2}$’s). However,
the optimal clustering would have cost 1 (by giving $x_{1}$ and $x_{2}$ the
same label and giving $x_{3}$ the remaining label). Again, this results in
competitiveness that can only be bounded by the aspect ratio of metric space
(much larger than $n$ or $k$).

Intuitively, the dilemma faced by the online algorithm when $x_{2}$ arrives is
that it does not know whether the distance between $x_{1}$ and $x_{2}$ is
small or large. Equipped with an estimate of the optimal cost $B$, the
algorithm could resolve this dilemma by giving $x_{2}$ a different label than
$x_{1}$ if their distance is larger than $B$ and the same label otherwise.
Thus we will assume that the algorithm is provided a priori with a budge $B$
that is an upper bound on the optimal cost (and ideally is not too much larger
than the optimal cost).

To better understand the design of our algorithm it is useful to understand
some instances that illustrate some properties that a competitive algorithm
must have.

The first observation is that any reasonably competitive algorithm can never
use $t+1$ labels if it is the case that the points to date could be clustered
with cost at most $B$ using at most $t$ labels. If the algorithm ever allowed
this to happen, it could be that the next $k-t$ data points could arrive very
far from the previous data points, and very far from each other. Thus after
these data points arrive, the algorithm’s cost would increase to something
like the diameter of the metric space, while there would still be a clustering
of cost at most $B$, since the clustering that used $t$ labels could be
extended with no additional cost by giving each new $k-t$ data points a new
label.

In light of this last observation, a natural greedy algorithm would maintain
the invariant that the number of labels it uses is always equal to the minimum
number of labels necessary for a clustering of cost at most $B$, and then give
each new data point the label that minimizes the increase in cost. To see why
such an algorithm (and other similar algorithms) can have unbounded cost even
when $k=2$, and the metric space is the real line, consider the following
instance (see Figure 1). Let $\alpha$ be an arbitrarily large positive
integer. We construct an example in which the budget $B=2$. The first point
arrives at location $-2$. Say the algorithm gives this point the label blue.
The next point arrives at location $1$. Now, we know that any offline
clustering with cost at most $2$ must use at least 2 clusters. So the greedy
algorithm would give this new point a second label, say green, as that would
minimize the increase in the objective. Then a total of $\alpha$ additional
points arrive at location $1$. The algorithm labels these points green. Then
$\alpha$ points arrive at the origin 0. It is still the case that only 2
clusters are required in order to have cost at most $2$, since we may place
the points at location $-2$ and the origin in one cluster, and the points at
location 1 in the other cluster. However the algorithm would assign each point
arriving at the origin the label green, since this increases the objective by
at most $1$ while assigning such a point the label blue increases the
objective by $2$. Yet, this results in a solution for the algorithm in which
the contribution of green points towards the objective is $\alpha$.

Figure 1: An example in which the natural greedy algorithm incurs arbitrarily
large cost.

Upon reflection of this lower bound instance for the natural greedy algorithm,
there appear to us to be two natural hypotheses as to the “mistake” that this
algorithm is making, and corresponding two natural paths towards a remedy:

  * •

One hypothesis is that greedy assignment is a mistake, and then the natural
remedy would be to use some label assignment rule that is more sophisticated
than greedy.

  * •

Another hypothesis is that the algorithm was too hasty in using a new label.
Thus the natural remedy would then be to delay using a new label until it is
more clear as to a region where arriving data points should be given this new
label. Note in the example in Figure 1 that if the algorithm had waited until
some reasonable number of data points had arrived at the origin before using
the second label, then the algorithm might reasonably have been able to see
that the right choice was to give the remaining points arriving at the origin
the second label of green.

Here we primarily adopt the second remedy/approach (although we also consider
an alternate greedy assignment policy). To apply this remedy we must address
the following two questions:

  * •

Under what conditions can the algorithm justify the use of an additional
label, say going from $t-1$ labels to $t$ labels?

  * •

And when this can be justified, how should we modify our prior partition of
space into $t-1$ parts into a partition into $t$ parts?

At a high level our answer to the first question is that we do not use $t$
labels until there exist $t$ well-separated points
$x_{\alpha(1)},\ldots,x_{\alpha(t)}$. We will say that a collection of points
$x_{\alpha(1)},\ldots,x_{\alpha(t)}$ from a collection $S$ of points is
$\beta$-well-separated with respect to $w_{S}$ if

$\min\\{w_{S}(x_{\alpha(i)}),w_{S}(x_{\alpha(j)})\\}\cdot
d(x_{\alpha(i)},x_{\alpha(j)})\geq\beta\cdot B\hskip 8.5359pt\text{for all
}i,j\in[t],i\neq j$ ($\star$)

Here $w_{S}(x_{h})$ is what we call the natural weight of point $x_{h}$ in
$S$, which is the maximum number of points in $S$ whose distances to $x_{h}$
sum to at most $2B$. (If $S$ is clear, we may drop it from the notation).
Intuitively, if we have $t$ well-separated points then we then know that not
only must any near optimal solution use $t$ labels, but such a solution cannot
combine the points near $x_{\alpha(i)}$ and the points near $x_{\alpha(j)}$
into a single cluster (assuming $i\neq j$).

To drill down a bit further, we maintain a collection of points
$p_{1},\ldots,p_{t}$ from the online stream $X$ which we call pivots. When a
new point arrives, it is assigned the label $i$ of the pivot $p_{i}$ nearest
to it (so we still maintain a form of greedy label assignment). While one
might reasonably think that the pivots are intuitively centers for the
clusters, this intuition is only partially correct. In fact there are
scenarios where some pivots are in fact poor centers for the corresponding
cluster. What is critical is that the pivots are located so as to guarantee
that using greedy assignment in the future results in a relatively low cost
assignment. In order for our cost analysis to be tractable we want the
algorithm to maintain the following invariants:

  * •

Each pivot $p_{i}$ is reasonably located in a region where it would not be too
costly to assign points arriving in this region the label $i$.

  * •

The pivots are well-separated (for some appropriate choice of
$\beta$).222$\beta$ will have to both be initialized sufficiently large and
also decrease as the number of pivots increases. We show this is necessary in
Appendix E.

  * •

There is no other point that is well-separated from the pivots.

  * •

The locations of the pivots should not move very often.

Note that some of these invariants can intuitively be in opposition to each
other, which seemingly requires that the design of the algorithm is a bit
complicated, as there are several different scenarios where maintaining this
invariant requires different actions. But we will now try to give a brief,
definitely over-simplified, overview of how the algorithm maintains these
invariants. As the pivots are not necessarily good centers (for example pivot
$p_{1}$ at location $-2$ as the points arrive at location 1 in Figure 1), the
algorithm also maintains a collection $c_{1},\ldots,c_{t}$ of estimated
centers for the $t$ labels that have been used to date. The pivots and the
estimated centers are updated in two scenarios. The first scenario is when
there is an applicable Add Operation, and the second is when there is an
applicable Exchange Operation. In both scenarios the estimated centers are
recomputed from the previously computed estimated centers and the newly
computed (near) optimal centers. Then a sequence of Add and Exchange
Operations are executed.

An Add Operation is applicable when there is a point $x_{\alpha}$ that is
well-separated from the current pivots. Intuitively, this means a new label
can be justified, but the implementation requires the consideration of several
possible scenarios. In the simplest scenario $x_{\alpha}$ is near a cluster of
new points that are all far from previous points, and the pivot $p_{t+1}$ for
the new label ($t+1$) is set to $x_{\alpha}$. In some scenarios an old pivot
$p_{i}$ ($i\leq t$) is set to $x_{\alpha}$ and $p_{t+1}$ is set to $p_{i}$ (so
the new pivot inherits an old label and an old pivot location gets the new
label). Intuitively, this occurs when the estimated center $c_{i}$ for cluster
$i$ is near the location of $x_{\alpha}$. Also there are scenarios where an
old pivot $p_{i}$ ($i\leq t$) is set to the estimated center $c_{i}$ of
cluster $i$ and $p_{t+1}$ is set to $p_{i}$ (so again the new pivot inherits
an old label and an old pivot location gets the new label). Finally, there are
scenarios where two new pivots are created.333This is needed to avoid label
conflicts. See Appendix F.

An Exchange Operation is applicable when there are two points $x_{\alpha}$ and
$x_{\gamma}$ near a pivot $p_{j}$ that are well-separated from each other and
the other pivots (besides $p_{j}$). So intuitively the cluster of points
labeled $j$ appear to be splitting into two clusters. In the simplest scenario
the location of pivot $p_{j}$ is set to the location of one of $x_{\alpha}$ or
$x_{\gamma}$, and the location of the new pivot $p_{t+1}$ is set to the
location of the other one. This scenario occurs in the instance depicted in
Figure 1. The first pivot $p_{1}$ is initially set to location $-2$. The
points arriving at location $1$ would all be assigned the label 1 (blue) as
there is no point well-separated from $p_{1}$ (the points located at $1$ are
not separated from $p_{1}$ because the points at $p_{1}$ can be cheaply moved
to location $1$). When enough points have arrived at the origin, then the
points $x_{\alpha}=0$ and at $x_{\gamma}=1$ are near $p_{1}$ (because the
point at $p_{1}$ can be cheaply moved to either $x_{\alpha}$ or $x_{\gamma}$),
and are well-separated from each other and the pivots other than $p_{1}$. Thus
our algorithm would locate $p_{1}$ at $1$ and $p_{2}$ at the origin. While
this scenario gives some intuition, there are several other more complicated
scenarios.

The analysis is broken into two parts. The first part is to show that certain
stuctural invariants are maintained through carefully engineered algorithmic
choices. The well-separated invariant is used to show we do not use more than
$k$ labels and for bounding the cost. The second part of the analysis is to
bound the cost (Section 6). We inductively assume that the cost of points that
were labelled using the first $t-1$ labels is bounded. Then, we show that the
points that were labelled when exactly $t$ labels were in use are clustered
near optimally under our greedy procedure. The key challenge is showing the
points given the same label combined have bounded cost.

##  3 Preliminaries

First we establish a lower bound depending on $k$ for the competitive ratio of
our algorithm.

######  Theorem 1.

The competitiveness versus the budget of any deterministic algorithm for
cluster-centric consistent clustering is $\Omega(k)$.

The proof of Theorem 1 is in Appendix B.

Assumptions. We only assume that the online stream $X$ lies in a metric space.
We allow multiple points to arrive at the same location; each duplicated point
still has to pay the cost to its nearest center. Whenever we refer to centers,
we enforce these come from $X$ itself. (This will be used to ensure our
algorithm is well-defined.)

We state our results assuming $B=\textsf{OPT}$, but all results still hold by
replacing OPT with $B$, as long as $\textsf{OPT}\leq B$. Our algorithm will
need to compute offline $k$-median clusterings; to do this in poly-time, use
any $c$-approximation algorithm. Thus, replace $B$ with $c\cdot B$ to run our
online algorithm in poly-time.

Terminology. Recall the term natural weight from Section 2. We will always
take $S$ to be some prefix of $X$. As such, we may refer to the natural
weights at a particular point in time to mean the natural weights in $S$,
where $S$ is the prefix at that time.

Note that for $p\in S$, $w_{S}(p)\geq 1$, since $d(p,p)=0$, and that
$w_{S}(p)$ can only increase over time as $S$ enlarges.

Recall the term $\beta$-well-separated from Section 2. Related terms we will
use are the following: We will say $p$ is $\beta$-well-separated from a set of
points $\\{x_{\alpha(1)},\dots,x_{\alpha(m)}\\}$ w.r.t. $w$ if
$\min\\{w(p),w(x_{\alpha(i)})\\}\cdot
d(p,x_{\alpha(i)})\geq\beta\cdot\textsf{OPT}$ for all $i\in[m]$. If $m=2$ and
the well-separated condition ($\star$ ‣ 2) is not satisfied, we say the pair
of points is $\beta$-attached, or that one is $\beta$-attached to the other,
w.r.t. $w$.

##  4 Algorithm Description

The algorithm sees an online sequence $X=\\{x_{1},x_{2},\ldots x_{n}\\}$ of
points. Let $X_{i}=\\{x_{1},x_{2},\ldots x_{i}\\}$ and $w_{i}$ be shorthand
for $w_{X_{i}}$. The algorithm maintains the following:

  * •

a collection of previously arriving points $p_{1},\dots,p_{t}$ that have been
designated as pivots, where $t$ is the number of labels used by the algorithm
to date and pivot $p_{j}$ is associated with label $j$,

  * •

a separation parameter $\beta_{t}=8\cdot 3^{k-t+2}$, and

  * •

a collection of previously arriving points $c_{1},\ldots,c_{T}$ that have been
designated as estimated centers, where $T\leq t$.

Initially the first point $x_{1}$ is given the label 1, the first pivot
$p_{1}$ is set to $x_{1}$, and the collection of estimated centers is empty.
The algorithm handles the arrival of each subsequent point $x_{i}$ in the
following manner. The subroutines are described in Sections 4.1, 4.2, 4.3.

  1. (1)

If there is an applicable Add or Exchange Operation then compute new Estimated
Centers

    1. (a)

Repeat while there is an applicable Add Operation or Exchange Operation

      1. i.

If there is an applicable Add Operation then apply an arbitrary applicable one

      2. ii.

Else apply an arbitrary applicable Exchange Operation

  2. (2)

Give $x_{i}$ the label $j$, where $p_{j}$ is the nearest pivot to $x_{i}$

Let $T$ be the number of pivots during an execution of the outer loop (1). The
Estimated Centers subroutine computes $T$ new estimated centers
$c_{1},\ldots,c_{T}$ from the current pivots $p_{1},\ldots p_{T}$, the points
$X_{i-1}$, and the current estimated centers $c_{1},\ldots c_{s}$ ($s<T$).

Let $t\geq T$ be the number of pivots during an execution of the inner loop
(a). The Add Operation subroutine is applicable if there is a point
$x_{\alpha}\in X_{i}$ such that $x_{\alpha}$ is $\beta_{t+1}$-well-separated
from the current pivots $p_{1},\dots,p_{t}$ with respect to the weight
function $w_{i}$. The execution of the Add Operation subroutine depends on
$x_{\alpha}$, $X_{i}$, the current pivots $p_{1},\ldots,p_{t}$, and the
current estimated centers $c_{1},\ldots,c_{T}$. The Add Operation subroutine
adds one or two new pivots, and possibly changes the location of up to two
previous pivots.

The Exchange Operation subroutine is applicable if there there exists two
points $x_{\alpha}$ and $x_{\gamma}$ in $X_{i}$, and a pivot $p_{j}$ such
that:

  * •

$x_{\alpha}$ and $x_{\gamma}$ are each $\beta_{t+1}$-attached to $p_{j}$
w.r.t. $w_{i}$,

  * •

$w_{i}(p_{j})\leq w_{i}(x_{\alpha})$,

  * •

$w_{i}(p_{j})\leq w_{i}(x_{\gamma})$, and

  * •

The collection of the $t+1$ points, consisting of $x_{\alpha}$, $x_{\gamma}$,
and the pivots other than $p_{j}$, are $\beta_{t+1}$-well-separated w.r.t.
$w_{i}$.

The execution of the Exchange Operation subroutine depends on $x_{\alpha}$,
$x_{\gamma}$, $X_{i}$, the current pivots $p_{1},\ldots,p_{t}$, and the
current estimated centers $c_{1},\ldots,c_{T}$. The Exchange Operation adds
one or two new pivots, and possibly changes the location of one previous
pivot.

###  4.1 The Estimated Center Subroutine

Choose $y_{1},\ldots,y_{k}\in X_{i-1}$ to be an optimal collection of $k$
centers for the points in $X_{i-1}$. (By Fact 1, there exists a collection
that gives a clustering of cost at most $2\textsf{OPT}$.) Define $p(y_{h})$ to
be the pivot with the minimum weighted distance to $y_{h}$, that is,

$p(y_{h})=\operatorname*{arg\,min}_{p_{j}}\left(\min\\{w_{i-1}(p_{j}),w_{i-1}(y_{h})\\}\cdot
d(p_{j},y_{h})\right)$ ($\dagger$)

For a pivot $p_{j}$, let $\delta(p_{j})$ be a collection of optimal centers
and estimated centers defined as follows: the current estimated center $c_{j}$
(when it exists) is in $\delta(p_{j})$ if $w_{i-1}(c_{j})>w_{i-1}(p_{j})$ and
$c_{j}$ is $\beta_{t+1}$-attached to $p_{j}$ w.r.t. $w_{i-1}$, and
$\delta(p_{j})$ contains an optimal center $y_{h}$ if
$w_{i-1}(y_{h})>w_{i-1}(p(y_{h}))$ for $p(y_{h})=p_{j}$. For each $j\in[T]$ we
define the new estimated center $c_{j}$ as follows: If
$w_{i-1}(p_{j})\geq\max_{p\in\delta(p_{j})}w_{i-1}(p)$ then $c_{j}=p_{j}$,
else

$\centering
c_{j}=\operatorname*{arg\,max}_{p\in\delta(p_{j})}w_{i-1}(p)\@add@centering$
($\ddagger$)

Figure 2: Left: The Estimated Center subroutine. Arrows point from smaller to
larger natural weights, and the small points around the larger points are the
the set attaining the weight of the larger point. Right: Case (1) of the Add
Operation. Dashed lines represent well-separation. Colors except black
represent labels. The pivot for label 2 (red) moves to location $c_{2}$, while
the old location for red’s pivot becomes the pivot of the new label (5,
brown).

###  4.2 The Add Operation Subroutine

For shorthand, let $w_{t}=w_{i-1}$ when $t=T$ and $w_{t}=w_{i}$ when
$t>T$.444We are overloading subscripts here for ease. We could instead write
$v_{t}$, but we retain $w$ to recall weights. The description of the Add
Operation subroutine is then:

  1. (1)

If there is an estimated center $c_{j}$ that is $\beta_{t+1}$-well-separated
from $p_{1},\dots,p_{t}$ w.r.t. $w_{i}$ then set $p_{t+1}=p_{j}$ and set
$p_{j}=c_{j}$.

  2. (2)

Else if it is the case that for every estimated center $c_{j}$ that is
$\beta_{t+2}$-attached to $x_{\alpha}$ w.r.t. $w_{i}$ it is also the case that
$w_{t}(c_{j})<w_{t}(p_{j})$, then set $p_{t+1}=x_{\alpha}$.

  3. (3)

Else if there exists a unique estimated center $c_{j}$ that both is
$\beta_{t+2}$-attached to $x_{\alpha}$ w.r.t. $w_{i}$ and satisfies
$w_{t}(c_{j})\geq w_{t}(p_{j})$, then set $p_{t+1}=p_{j}$ and
$p_{j}=x_{\alpha}$.

  4. (4)

Else Let $c_{f}$ and $c_{g}$ be estimated centers such that each is
$\beta_{t+2}$-attached to $x_{\alpha}$ w.r.t. $w_{i}$, $w_{t}(c_{f})\geq
w_{t}(p_{f})$, and $w_{t}(c_{g})\geq w_{t}(p_{g})$. Then set $p_{t+1}=p_{f}$,
$p_{t+2}=p_{g}$, $p_{f}=c_{f}$, and $p_{g}=c_{g}$.

Figure 3: Case (4) of the Add Operation. Dashed lines represent well-
separation while solid lines represent attachment, both w.r.t. $w_{i}$
(labelled with the appropriate $\beta$). The pivots for labels 2 (red) and 3
(green) move to $c_{2},c_{3}$, resp., while the old locations for these pivots
are where the new pivots 5 and 6 (brown and blue) are located.

###  4.3 The Exchange Operation Subroutine

The description of the Exchange Operation subroutine is:

  1. (1)

If $j>T$ then set $p_{j}=x_{\alpha}$ and $p_{t+1}=x_{\gamma}$.

  2. (2)

Else if $w_{i}(c_{j})<w_{i}(p_{j})$ then set $p_{j}=x_{\alpha}$ and
$p_{t+1}=x_{\gamma}$.

  3. (3)

Else if $c_{j}$ is $\beta_{t+2}$-attached to $x_{\alpha}$ w.r.t. $w_{i}$ then
set $p_{j}=x_{\alpha}$ and $p_{t+1}=x_{\gamma}$.

  4. (4)

Else if $c_{j}$ is $\beta_{t+2}$-attached to $x_{\gamma}$ w.r.t. $w_{i}$ then
set $p_{j}=x_{\gamma}$ and $p_{t+1}=x_{\alpha}$.

  5. (5)

Else set $p_{t+1}=x_{\alpha}$, $p_{t+2}=x_{\gamma}$, and $p_{j}=c_{j}$.

Figure 4: Dashed and solid lines and arrows are as in Figures 2 and 3. Colors
except black represent labels. Left: The configuration triggering the Exchange
Operation; dashed lines between $p_{1},\dots,p_{4}$ suppressed. Right: Case
(2) of the Exchange Operation. The old location for label 3’s (green’s) pivot
is no longer a pivot location, and label 3’s pivot is now $x_{\alpha}$. The
new label, label 5 (brown), has its pivot at $x_{\gamma}$.

##  5 Algorithm Guarantees and Invariants

We will establish two main guarantees for our algorithm and a set of
invariants the algorithm will maintain to establish these guarantees. The most
challenging and interesting algorithmic property is that the algorithm has
bounded cost. The second is that the algorithm is feasible. The theorem below
gives the cost guarantees; its proof is in Section 6. We state our results
assuming $B=\textsf{OPT}$, but all results still hold by replacing OPT with
$B$, as long as $\textsf{OPT}\leq B$.

######  Theorem 2.

The cost of the algorithm is $O(k^{5}\cdot 3^{k}\cdot\textsf{OPT})$.

The next theorem states that the algorithm never uses more than $k$ labels and
therefore produces a feasible solution. The proof of this theorem is in
Section 5.3.

######  Theorem 3.

The algorithm uses at most $k$ labels.

###  5.1 Notation and Definitions

We now define some notation and definitions used in the analysis.

  * •

Phase $t$ refers to the set of time steps during which there are exactly $t$
pivots.

  * •

$p_{1}^{t},\dots,p_{t}^{t}$ denote the pivots for labels 1 through $t$,
respectively, during phase $t$.

  * •

$w^{t}$ denotes the natural weights at the end of phase $t$.

  * •

$X(t)$ is the set of points assigned a label before or during phase $t$.

  * •

For $j\in[t]$, let $C_{j}^{t}$ denote denote the points labelled $j$ in phases
1 through $t$.

  * •

An intermediate phase $t$ is a phase during which no points are given labels.
This is a phase solely used to reset pivots.

  * •

A non-intermediate phase $T$ is a phase in which at least one point is given a
label.

For a non-intermediate phase $T$,

  * •

Let $T^{-}$ to denote the most recent non-intermediate phase before $T$, and
$T^{+}$ to denote the first non-intermediate phase after $T$ (when these
exist).555Using the notation in Section 4, $x_{i-1}$ is the last point
labelled during phase $T$, and $x_{i}$ is the first point labelled during
phase $T^{+}$.

  * •

For $j\in[T]$, $c_{j}^{T}$ is the estimated center ($\ddagger$ ‣ 4.1) computed
at the end of phase $T$.

  * •

Let $y_{1},\dots,y_{k}$ be the optimal collection of $k$ centers computed at
the end of phase $T$ in The Estimated Center Subroutine. Let
$P_{T}=\\{p_{1}^{T},\dots,p_{T}^{T},y_{1},\dots,y_{k}\\}$ and call this set
the offline centers for phase $T$.666Note that $c_{j}^{T}$ and $P_{T}$ are
only defined for non-intermediate phases $T$.

  * •

The attachment digraph $D(T)$ is a bipartite digraph with vertex set $P_{T}$,
plus $c_{j}^{T^{-}}$ if $T>1$, partitioned as
$(\\{p_{1}^{T},\dots,p_{T}^{T}\\},\\{y_{1},\dots,y_{k},c_{j}^{T^{-}}\\})$.
There is a directed arc $(y_{i},p(y_{i}))$ if $w^{T}(y_{i})\leq
w^{T}(p(y_{i}))$ and a directed arc $(y_{i},p(y_{i}))$ otherwise. If
$c_{j}^{T^{-}}$ and $p_{j}^{T}$ are $\beta_{T+1}$-attached w.r.t. $w^{T}$, add
the arc $(c_{j}^{T^{-}},p_{j}^{T})$ if $w^{T}(c_{j}^{T^{-}})\leq w(p_{j}^{T})$
and the arc $(p_{j}^{T},c_{j}^{T^{-}})$ otherwise. $\delta^{+}(p_{j}^{T})$ and
$\delta^{-}(p_{j}^{T})$ denote the out-degree and in-degree of $p_{j}^{T}$,
respectively.

###  5.2 Invariants

The first property of our algorithm is that it maintains pivots that are
sufficiently far apart with respect to their natural weights. This is at the
heart of our analysis for both controlling the number of labels used and the
algorithm’s cost.

######  Lemma 1.

Let $t\in[k]$. The algorithm maintains the invariant that
$p_{1}^{t},\dots,p_{t}^{t}$ are $\beta_{t}$-well-separated w.r.t. the natural
weights at the start of phase $t$ (and thereafter).777Two points well-
separated at one time step will also be well-separated at a later time step,
since their natural weights can only increase and the well-separation
parameter $\beta_{t}$ can only decrease.

The next lemma is a key technical lemma. It states that the estimated center
($\ddagger$ ‣ 4.1) for the points given label $j$ before phase $T$ is close,
in a weighted sense, to the pivot for label $j$ in phase $T$. This is key to
showing that points in cluster $j$ that are labelled before phase $T$ can be
combined with those that are labelled during phase $T$ at bounded cost. This
lemma is in tension with the prior lemma because a pivot must be placed in a
location where it is both well-separated from other pivots and is close to
center of mass of the points of a given label.

######  Lemma 2.

Let $T$ be a non-intermediate phase and let $j\in[T]$. Let $w^{t}$ denote the
natural weights at the end of phase $t$. If $T>1$, then at least one of the
following holds:

  1. (a)

$w^{T^{-}}(c_{j}^{T^{-}})\leq w^{T}(p_{j}^{T})$ and
$w^{T^{-}}(c_{j}^{T^{-}})\cdot
d(c_{j}^{T^{-}},p_{j}^{T})\leq\beta_{T^{-}}(T-T^{-})\cdot\textsf{OPT}$, or

  2. (b)

$c_{j}^{T^{-}}$ is $\beta_{T+1}$-attached to $p_{j}^{T}$ w.r.t. $w^{T}$.

###  5.3 Proof of the Algorithm’s Feasibility and the Invariants

We begin by showing a bound on the number of well-separated points in the
entire point set. Lemma 1 along with Proposition 1 below will immediately
imply Theorem 3, which states that the algorithm uses at most $k$ labels.

######  Proposition 1.

Let $X$ be a set of points whose optimal $k$-median cost using $k$ centers is
OPT. Let $\\{x_{1},\dots,x_{l}\\}$ be a set of points in $X$, and let $w_{X}$
denote their natural weights in $X$. Let $\beta>8$. If
$\\{x_{1},\dots,x_{l}\\}$ is $\beta$-well-separated w.r.t. $w_{X}$, then
$l\leq k$.

###### Proof of Proposition 1.

For shorthand, let $w_{i}=w_{X}(x_{i})$. By Markov’s inequality, for each
$i\in[l]$ there must be at least $w_{i}/2$ points from $X$ inside
$B(x_{i},2\textsf{OPT}/w_{i})$. Consider a clustering on $X$ with cost OPT
using $k$ centers. Then each ball $B(x_{i},4\textsf{OPT}/w_{i})$ must contain
at least one of these $k$ centers; for, if not, then at least $w_{i}/2$ points
inside $B(x_{i},2\textsf{OPT}/w_{i})$ must each pay strictly more than
$2\textsf{OPT}/w_{i}$ to reach a center. This contradicts that the optimal
$k$-median cost is OPT.

Now it remains to show, using the well-separation assumption, that these balls
are disjoint; this will imply that $l\leq k$, since each ball must contain a
center. Suppose to the contrary that there exist $i,j\in[l]$, $i\neq j$, such
that $p\in B(x_{i},4\textsf{OPT}/w_{i})\cap B(x_{j},4\textsf{OPT}/w_{j})$.
Applying the triangle inequality gives

$\displaystyle d(x_{i},x_{j})\leq d(p,x_{i})+d(p,x_{j})$
$\displaystyle\leq\frac{4\textsf{OPT}}{w_{i}}+\frac{4\textsf{OPT}}{w_{j}}\leq\frac{8\textsf{OPT}}{\min\\{w_{i},w_{j}\\}}$

which contradicts that $\\{(x_{i},w_{i}),(x_{j},w_{j})\\}$ is $\beta$-well-
separated, i.e., that $\min\\{w_{i},w_{j}\\}\cdot
d(x_{i},x_{j})\geq\beta\textsf{OPT}$, since $\beta>8$. ∎

The next two propositions will be used to aid the proofs of Lemmas 1 and 2.
Recall that for each non-intermediate phase $T$, we defined a set of offline
centers $P_{T}$ that has cost at most $2\textsf{OPT}$ on $X(T)$ (Section 5.1).
In order to compare the (low-cost) offline clustering induced by $P_{T}$ to
our online algorithm’s clustering, we relate the offline set of centers
$P_{T}$ (which we know have bounded cost on $X(T)$) to the pivots in phase $T$
(which are used to make the greedy online choices) in the next proposition.

######  Proposition 2.

Let $P_{T}=\\{p_{1}^{T},\dots,p_{T}^{T},y_{1},\dots,y_{k}\\}$ be as in Section
5.1. Then $y_{i}$ and $p(y_{i})$ are $\beta_{T+1}$-attached w.r.t. the natural
weights $w^{T}$ at the end of phase $T$.

###### Proof of Proposition 2.

First we show that $y_{i}$ is $\beta_{T+1}$-attached to at least one of
$p_{1}^{T},\cdots,p_{T}^{T}$ w.r.t. $w^{T}$. Suppose not. Then an Add
Operation would have been executed instead, and phase $T$ would have
terminated in the previous time step, which is a contradiction. That $y_{i}$
is $\beta_{T+1}$-attached to $p(y_{i})$ in particular follows directly from
the definition ($\dagger$ ‣ 4.1) of $p(y_{i})$ as the pivot with the minimum
weighted distance to $y_{i}$. ∎

Observe that the proof of Proposition 2 is a direct consequence of the fact
that we always execute an Add Operation or an Exchange Operation when one is
available, so during a phase none are available. Each attached pair in
Proposition 2 is encoded in the digraph $D(T)$ by a directed arc. Due to
Proposition 2, we can now think of this directed arc as representing the
direction in which we could move a certain number of points sitting near one
endpoint to the other endpoint at bounded cost.

Algorithmically, we used $P_{T}$ to define the estimated centers $c_{j}^{T}$
($\ddagger$ ‣ 4.1). Next we show that the estimated center for a cluster at
the end of a phase is attached to the pivot for that cluster in that phase.
Thus, while the pivot itself may not be a good center for the cluster, the
pivot is close to the estimated center (in at least one direction, in a
weighted sense).

######  Proposition 3.

The estimated center $c_{j}^{T}$ is $\beta_{T+1}$-attached to $p_{j}^{T}$
w.r.t. the natural weights $w^{T}$ at the end of phase $T$. Further,
$w^{T}(c_{j}^{T})\geq w^{T}(p_{j}^{T})$, with equality if and only if
$c_{j}^{T}=p_{j}^{T}$.

The proof of Proposition 3 is a straightforward consequence of Proposition 2
and the definition ($\ddagger$ ‣ 4.1) of estimated center; for completeness,
it can be found in Appendix C.

Using these propositions, we establish Lemma 1, used heavily in our analysis.
The full proof is involved, so we defer it to Appendix C and provide a sketch
of the key ideas here.

###### Proof sketch of Lemma 1..

The proof is by induction. However, we need to couple the induction with a
statement about the relative position of the estimated center for a cluster
(which stays fixed between intermediate phases) to that cluster’s pivot, which
may change often as we consecutively reset the pivots between intermediate
phases. Roughly, we prove below that if the estimated center for cluster $j$
has not separated entirely from the present set of pivots, then it must be
close (in a weighted sense) to the present pivot for label $j$.

######  Proposition 4.

Let $w_{i-1}$, $w_{i}$, and $w_{t}$ be as Section 4.2. For each $j\in[T]$ and
$t\in[T,T^{+}]$ such that $p_{1}^{t},\cdots,p_{t}^{t}$ are defined,888Recall
in Case 4 of the Add Operation and Case 5 of the Exchange Operation, we go
directly from $t$ to $t+2$ pivots, skipping phase $t+1$.

$p_{1}^{t},\dots,p_{t}^{t}\text{ are }\beta_{t}\text{-well-separated w.r.t.
}w_{t}.$ ($\Diamond$)

Moreover, at least one of the following properties holds:

  1. (a)

$c_{j}^{T}$ is $\beta_{t+1}$-well-separated from $p_{1}^{t},\dots,p_{t}^{t}$
w.r.t. $w_{i}$.

  2. (b)

$c_{j}^{T}$ is $\beta_{t+1}$-attached to $p_{j}^{t}$ w.r.t. $w_{t}$.

  3. (c)

$c_{j}^{T}$ is $f(t,T)$-attached to $p_{j}^{t}$ w.r.t. $w_{t}$ and
$w_{t}(c_{j}^{T})<w_{t}(p_{j}^{t})$, where $f(t,T)={\beta_{T}\cdot(t-T)}$.

For the proof sketch we focus on Case 4 of the Add Operation, which will give
a flavor of the arguments. This is a concerning case a priori; for, if we were
to add $x_{\alpha}$ to the set of pivots as in Cases 2 and 3, it is ambiguous
as to whether $x_{\alpha}$ should be associated with label $f$ or $g$, as both
$c_{f}^{T}$ and $c_{g}^{T}$ are close to $x_{\alpha}$ (see Appendix F for a
diagram). We maneuver around the issue by making $c_{f}^{T}$ and $c_{g}^{T}$
new pivots and excluding $x_{\alpha}$. However, it is not immediately clear
that such a step will preserve the desired invariants. To give intuition, we
suppress the separation parameters and the precise weights used, though
emphasize both are brittle (e.g., the arguments rely heavily on $\beta_{t}$
decreasing with $t$, see also Appendix E). The directions of attachment
between points (arrows in Figure 5) are also crucial. We will also see why we
need to couple the induction with (a)—(c).

To prove the inductive step for ($\Diamond$ ‣ 4) when Case 4 of the Add
Operation is performed, we need to show (i) $c_{f}^{T}$ and $c_{g}^{T}$ are
well-separated, (ii), WLOG, $c_{f}^{T}$ is well-separated from $p_{f}^{t}$,
and (iii), WLOG, $c_{f}$ is well-separated from $p_{l}^{t}$, $l\neq f$. See
Figure 5. When we say “close” or “far” below, we always mean in a weighted
sense. For (i), because $p_{f}^{T}$ is close to $c_{f}^{T}$ (Proposition 3)
and likewise for $p_{g}^{T}$, $c_{g}^{T}$, then $c_{f}^{T}$ and $c_{g}^{T}$
cannot be close, since this would violate that $p_{f}^{T}$ and $p_{g}^{T}$ are
(inductively) far. To prove (ii), note $x_{\alpha}$ is far from $p_{f}^{t}$ by
assumption of the Add Operation, and $c_{f}^{T}$ is close to $x_{\alpha}$ by
assumption of Case 4, so $p_{f}^{t}$ and $c_{f}^{T}$ must be far. Finally for
(iii), one can (inductively) deduce that (b) must hold when $j=f$, so
$c_{f}^{T}$ and $p_{f}^{t}$ are close; but, since $p_{f}^{t}$ and $p_{l}^{t}$
are (inductively) far, $c_{f}^{t}$ and $p_{l}^{t}$ must be far.

Proving the inductive step for (a)—(c) involves detailed casework. The Add and
Exchange Operations are engineered so that, loosely speaking, an estimated
center is either attached to the corresponding present pivot, or else breaks
off to form its own pivot. A main subtlety is the direction and strength of
attachment, e.g., property (c). Another is the sequence of operations,
specifically, the Add Operation taking precedence over the Exchange Operation.
∎

Figure 5: Cases (i)—(iii) in the proof sketch of Lemma 1. Dashed lines
indicate well-separation and solid lines indicate attachment, labelled with
the appropriate parameters. Arrows go from smaller to larger natural weights.

Theorem 3 follows from Lemma 1 and Proposition 1 once we observe that we have
set $\beta_{1}$ sufficiently large. For completeness, we include the proof
below.

###### Proof of Theorem 3.

The number of labels used by the algorithm is the number of pivots in the last
phase. By Lemma 1, we maintain the invariant that pivots
$p_{1}^{t},\dots,p_{t}^{t}$ are $\beta_{t}$-well-separated w.r.t. the natural
weights at every time step in phase $t$. Suppose to the contrary that the
final number of pivots is strictly more than $k$. Then at some point there are
$t=k+1$ or $t=k+2$999The algorithm may skip a phase, hence we consider both
cases. pivots that are $\beta_{t}$-well-separated w.r.t. the natural weights
throughout phase $t$. But $\beta_{k+2}=8$, and it is impossible for $k+2$
points to be 8-well-separated, by Proposition 1. We conclude the final number
of pivots is at most $k$, so the algorithm uses at most $k$ labels. ∎

As the proof of Proposition 4 shows, the Add and Exchange operations are
engineered so that the estimated center $c_{j}^{T^{-}}$ is close to
$p_{j}^{T}$ at the beginning of phase $T$. Lemma 2 states that this property
is maintained through the end of phase $T$. In essence, this is because no Add
or Exchange operations are executed during phase $T$, so we can show that the
attachment between $c_{j}^{T^{-}}$ and $p_{j}^{T}$ is static—even as natural
weights increase. The proof is below.

###### Proof of Lemma 2.

We need to show that: either $w^{T}(c_{j}^{T})\leq w^{T^{+}}(p_{j}^{T^{+}})$
and $w^{T}(c_{j}^{T})\cdot
d(c_{j}^{T},p_{j}^{T^{+}})\leq\beta_{T}(T^{+}-T)\cdot\textsf{OPT}$, or
$c_{j}^{T}$ is $\beta_{T^{+}+1}$-attached to $p_{j}^{T^{+}}$ w.r.t.
$w^{T^{+}}$.

We need the second part of Proposition 4. When we reach the start of phase
$T^{+}$, there are no Add Operations or Exchange Operations available, so (a)
in the statement of Proposition 4 cannot hold when $t=T^{+}$. Thus either (b)
or (c) must hold.

Let $w_{T^{+}}$ denote the natural weights at the start of phase $T^{+}$. Note
this notation is consistent with taking $t=T^{+}$ in $w_{t}$ in Proposition 4.

######  Case 1.

In Proposition 4, (c) holds.

If (c) holds, then

$w^{T}(c_{j}^{T})\leq w_{T^{+}}(c_{j}^{T})<w_{T^{+}}(p_{j}^{T^{+}})\leq
w^{T^{+}}(p_{j}^{T^{+}}),\hskip 8.5359pt\text{and}$ $w^{T}(c_{j}^{T})\cdot
d(c_{j}^{T},p_{j}^{T^{+}})\leq w_{T^{+}}(c_{j}^{T})\cdot
d(c_{j}^{T},p_{j}^{T^{+}})\leq\beta_{T}(T^{+}-T)\cdot\textsf{OPT}$

where the second inequality in the first line and the last inequality in the
second line follow from (c) holding in Proposition 4.

######  Case 2.

In Proposition 4, (c) does not hold.

If (c) does not hold, then $w_{T^{+}}(c_{j}^{T})\geq w_{T^{+}}(p_{j}^{T^{+}})$
and $c_{j}^{T}$ is $\beta_{{T^{+}}+1}$-attached to $p_{j}^{T^{+}}$ w.r.t.
$w_{T^{+}}$, i.e., the weights at the beginning of phase $T^{+}$ (since
$\beta_{T^{+}+1}<\beta_{T}(T^{+}-T)$). We need to show that $c_{j}^{T}$ is
$\beta_{{T^{+}}+1}$-attached to $p_{j}^{T^{+}}$ w.r.t. $w^{T^{+}}$, i.e., the
weights at the end of phase $T^{+}$. Recall that through the end of phase
$T^{+}$, $c_{j}^{T}$ remains $\beta_{{T^{+}}+1}$-attached to at least one of
the ${T^{+}}$ pivots (otherwise, the phase would terminate and an Add
Operation would be executed). So it just remains to show that at the end of
phase ${T^{+}}$, $c_{j}^{T}$ is still $\beta_{{T^{+}}+1}$-attached to
$p_{j}^{T^{+}}$ in particular, w.r.t. $w^{T^{+}}$. Suppose to the contrary
that $c_{j}^{T}$ is $\beta_{{T^{+}}+1}$-attached to $p_{j^{\prime}}^{T^{+}}$
w.r.t. $w^{T+}$, where $j^{\prime}\neq j$. Then it must be the case that
$c_{j}^{T}$ is $\beta_{{T^{+}}+1}$-attached to $p_{j^{\prime}}^{T^{+}}$ w.r.t.
$w_{T+}$. But we also know that $w_{T^{+}}(c_{j}^{T})\geq
w_{T^{+}}(p_{j}^{T^{+}})$ and $c_{j}^{T}$ is $\beta_{{T^{+}}+1}$-attached to
$p_{j}^{T^{+}}$ w.r.t. $w_{T^{+}}$. By Proposition 5, this contradicts that
$p_{j}^{T^{+}}$ and $p_{j^{\prime}}^{T^{+}}$ are $\beta_{T^{+}}$-well-
separated w.r.t. $w_{T^{+}}$.

∎

Having established Lemma 2, we are ready to bound the cost of the algorithm,
using the present pivot $p_{j}^{T}$ as the “bridge” between old and newly
arriving points given label $j$. We will show inductively that, at bounded
cost, we can move the old points to $c_{j}^{T^{-}}$, which is in some sense
close to $p_{j}^{T}$ by Lemma 2. In turn, $p_{j}^{T}$ dictates the greedy
choices for the new points. So we will combine the cost of old and new points
via $p_{j}^{T}$.

##  6 Bounding the Algorithm’s Cost

Throughout, let $cost(S;c)=\sum_{p\in S}d(p,c)$ for $S\subseteq X$ and $c\in
X$.

As a first step, we need to bound the cost contribution of points that arrive
during a single phase. The strategy is to compare the online greedy choices
with the offline optimal choices, and to show these are sufficiently similar.
More specifically, we know that in $D(T)$ each offline optimal center $y_{i}$
in $P_{T}$ is in the neighborhood of exactly one pivot, namely $p(y_{i})$, and
$y_{i}$ and $p(y_{i})$ are close in a weighted sense, i.e., attached
(Proposition 2). We further know that since no Exchange Operations are
executed during a phase, we can show that if $y_{i_{1}}$ and $y_{i_{2}}$ are
in the neighborhood of the same pivot ($p(y_{i_{1}})=p(y_{i_{2}})$), then
$y_{i_{1}}$ and $y_{i_{2}}$ are also close in a weighted sense.

Using these facts, we would be in good shape if we could show that for every
point arriving during phase $T$, it is the case that if the point is assigned
to $y_{i}$ in the offline optimal solution, then it receives the label of
pivot $p(y_{i})$ online. While this is not quite true, we can instead show
that the number of points that do not satisfy this condition is small relative
to the natural weights of their pivot, owing to the well-separated invariant
(Lemma 1). Further, we show that these points can still be moved to their
pivots at bounded cost, due to the greedy labelling rule. In effect, we will
charge the cost of these “far” points to their pivot. Lemma 3 summarizes this
argument, and is used to prove the main theorem, Theorem 2.

######  Lemma 3.

Let $T$ be a non-intermediate phase. For any $j\in[T]$, let $C_{j}$ be the
points given label $j$ during phase $T$, i.e., $C_{j}=C_{j}^{T}\setminus
C_{j}^{T^{-}}$. Define $S_{ji}$ to be be the set of elements in $C_{j}$
assigned to $y_{i}$ in the clustering of $X(T)\setminus X(T^{-})$ induced by
$P_{T}$. Define $S_{far,j}=\bigcup_{i:p(y_{i})\neq p_{j}^{T}}S_{ji}$. Then

  1. 1.

$cost(S_{far,j};p_{j}^{T})\leq k\cdot(\beta_{T+1}+2)\cdot\textsf{OPT}$, and

  2. 2.

$|S_{far,j}|\leq k\cdot w^{T}(p_{j}^{T})$, where $w^{T}$ denotes the natural
weights at the end of phase $T$.

The following lemma states that the number of points in a cluster by the end
of any phase is a bounded factor away from the natural weight (at the end of
the phase) of the estimated center for that cluster at the end of the phase.

######  Lemma 4.

Let $T$ be a non-intermediate phase and $j\in[T]$. Let $w^{T}(c_{j}^{T})$
denote the natural weight of $c_{j}^{T}$ at the end of phase $T$ and let
$C_{j}^{T}$ denote the set of points in cluster $j$ by the end of phase $T$.
Then

$|C_{j}^{T}|\leq(2k+1)\cdot T\cdot w^{T}(c_{j}^{T}).$

######  Lemma 5.

Let $T$ be a non-intermediate phase and $j\in[T]$. Then $cost(C_{j}^{T})$ is
bounded against center $c_{j}^{T}$, i.e.,

$\sum_{x\in C_{j}^{T}}d(x,c_{j}^{T})\leq g(T,k)\cdot\textsf{OPT},\hskip
5.69046ptg(T,k)=T\cdot g(k),\hskip
2.84544ptg(k)=\beta_{1}(2k^{3}+3k^{2}+5k+1)+2k+4.$

As a corollary to Lemma 5, we have Theorem 2, the main theorem.

Broadly, here is how the Lemmas 2, 3, and 4 will tie together to prove Lemma
5. The proof of Lemma 5 is by induction. Inductively, the points in cluster
$j$ that arrived before phase $T$, which we call $C_{j}^{T^{-}}$, can be moved
to their estimated center $c_{j}^{T^{-}}$ at bounded cost. This estimated
center is close to $p_{j}^{T}$ by Lemma 2. For instance, (a) in Lemma 2 says
that once the points in $C_{j}^{T^{-}}$ are moved to $c_{j}^{T^{-}}$, they can
also be moved to $p_{j}^{T}$ at bounded cost, since
$w^{T^{-}}(c_{j}^{T^{-}})\cdot d(c_{j}^{T^{-}},p_{j}^{T})$ is bounded and
$|C_{j}^{T^{-}}|\leq h(T^{-},k)\cdot w^{T^{-}}(c_{j}^{T^{-}})$ (Lemma 4).
Finally, since $w^{T^{-}}(c_{j}^{T^{-}})\leq w^{T}(p_{j}^{T})$, we will be
able to charge the points in $C_{j}^{T^{-}}$ to $p_{j}^{T}$ in order to move
them to $c_{j}^{T}$, which is attached to $p_{j}^{T}$ (Proposition 3). By
similar logic, the cost of the far points $S_{far,j}$ from phase $T$ can be
charged to $p_{j}^{T}$ and then moved to $c_{j}^{T}$ (Lemma 3). Finally, the
remaining points given label $j$ in phase $T$, call them $S_{near,j}$, are
close to offline centers in $P_{T}$ that are in turn close to $p_{j}^{T}$.
Crucially, no Exchange Operation is executed during a phase, so these offline
centers are also close to $c_{j}^{T}$ in a weighted sense.

###  6.1 Proofs for bounding cost

We start with the proof of Lemmas 3, which is a key step where the greedy rule
for assigning labels to points is used.

###### Proof of Lemma 3.

WLOG, let $j=T$. For $c\in P_{T}$, let $m(c)$ be the number of points assigned
to $c$ in the clustering of $X(T)\setminus X(T^{-})$ induced by the centers
$P_{T}$, i.e., in this clustering every point is assigned to the nearest point
in $P_{T}$.

For shorthand, let $w$ denote the natural weights $w^{T}$ of points at the end
of phase $T$.

######  Observation 1.

For $c\in P_{T}$, $w(c)\geq m(c)$.

This follows from the definition of $w(c)$ and the fact that there are $m(c)$
points whose movement cost to $c$ is at most $2\textsf{OPT}$, by construction
of $P_{T}$.

######  Observation 2.

If $(p(y_{i}),y_{i})$ is a directed edge in $D(T)$, then $w(p(y_{i}))\cdot
d(p(y_{i}),y_{i})<\beta_{T+1}\cdot\textsf{OPT}$. Likewise, if
$(y_{i},p(y_{i}))$ is a directed edge in $D(T)$, then $w(y_{i})\cdot
d(p(y_{i}),y_{i})<\beta_{T+1}\cdot\textsf{OPT}$.

This follows from the definition of $D(T)$ and Proposition 2.

Call the points in $S_{far,T}$ far points. In the claims below, we show that
the far points can be moved to $p_{T}^{T}$ at bounded cost (Claims 1 and 2),
and that there are not too many far points relative to the weight of
$p_{T}^{T}$ (Claim 3). In turn, we will be able to charge the cost of the far
points to $p_{T}^{T}$.

######  Claim 1.

Let $p(y_{i})\neq p_{T}^{T}$. Suppose $w(y_{i})>w(p(y_{i}))$. Then
$cost(S_{Ti};p_{T}^{T})\leq{(\beta_{T+1}+2)}\textsf{OPT}$.

###### Proof.

WLOG, let $p(y_{i})=p_{1}^{T}$. We consider two cases.

######  Case 1.

$|S_{Ti}|\geq w(p_{1}^{T})$. We will show this case cannot happen.

In this case, we know that $w(y_{i})\geq m(y_{i})\geq|S_{Ti}|\geq
w(p_{1}^{T})$. We know by Observation 2 that ${w(p_{1}^{T})\cdot
d(p_{1}^{T},y_{i})<\beta_{T+1}\cdot\textsf{OPT}}$. By Proposition 5, this
implies $w(p_{1}^{T})\cdot d(y_{i},p_{T}^{T})\geq
2\beta_{T+1}\cdot\textsf{OPT}$.

Since $|S_{Ti}|\geq w(p_{1}^{T})$, there exists $S_{Ti}^{\prime}\subseteq
S_{Ti}$ such that $|S_{Ti}^{\prime}|=w(p_{1}^{T})$. In turn,
$cost(S_{Ti}^{\prime};p_{1}^{T})\leq
cost(S_{Ti}^{\prime};y_{i})+w(p_{1}^{T})\cdot
d(y_{i},p_{1}^{T})<(\beta_{T+1}+2)\cdot\textsf{OPT}$, since $P_{T}$ is a
clustering with cost at most $2\textsf{OPT}$. On the other hand,

$cost(S_{Ti}^{\prime};p_{T}^{T})\geq\sum_{p\in
S_{Ti}^{\prime}}d(y_{i},p_{T}^{T})-\sum_{p\in
S_{Ti}^{\prime}}d(p,y_{i})=w(p_{1}^{T})\cdot d(y_{i},p_{T}^{T})-\sum_{p\in
S_{Ti}^{\prime}}d(p,y_{i})\geq(2\beta_{T+1}-2)\textsf{OPT}.$

Since $\beta_{T+1}\geq 4$, $\beta_{T+1}+2\leq 2\beta_{T+1}-2$, so
$cost(S_{Ti}^{\prime};p_{1}^{T})<cost(S_{Ti}^{\prime};p_{T}^{T})$, which
violates that $T=\arg\min_{j\in[T]}d(p,p_{j}^{T})$ for all $p\in
S_{Ti}^{\prime}\subseteq C_{T}$.

######  Case 2.

$|S_{Ti}|\leq w_{t}(p_{1}^{T})$.

In this case, we know that since $w(p_{1}^{T})\cdot
d(y_{i},p_{1}^{T})<\beta_{T+1}\cdot\textsf{OPT}$, we also have $|S_{Ti}|\cdot
d(y_{i},p_{1}^{T})<\beta_{T+1}\cdot\textsf{OPT}$. By the triangle inequality,

$cost(S_{Ti};p_{1}^{T})\leq cost(S_{Ti};y_{i})+|S_{Ti}|\cdot
d(y_{i},p_{1}^{T})\leq 2\textsf{OPT}+\beta_{T+1}\cdot\textsf{OPT}.$

Since $cost(S_{Ti};p_{T}^{T})\leq cost(S_{Ti};p_{1}^{T})$ by the greedy
procedure, this proves Claim 1. ∎

######  Claim 2.

Let $p(y_{i})\neq p_{T}^{T}$. Suppose that $w(y_{i})\leq w(p(y_{i}))$. Then
$cost(S_{Ti};p_{T}^{T})\leq{(\beta_{T+1}+1)}\textsf{OPT}$.

###### Proof.

WLOG, let $p(y_{i})=p_{1}^{T}$. By Observation 2, $w(y_{i})\cdot
d(y_{i},p_{1}^{T})<\beta_{T+1}\cdot\textsf{OPT}$. Further, $|S_{Ti}|\leq
m(y_{i})\leq w(y_{i})$, so $|S_{Ti}|\cdot
d(y_{i},p_{1}^{T})<\beta_{T+1}\cdot\textsf{OPT}$. So:

$cost(S_{Ti};p_{T}^{T})\leq cost(S_{Ti};p_{1}^{T})\leq
cost(S_{Ti};y_{i})+|S_{Ti}|\cdot d(y_{i},p_{1}^{T})\leq
2\textsf{OPT}+\beta_{T+1}\cdot\textsf{OPT}.$

∎

######  Claim 3.

Let $p(y_{i})\neq p_{T}^{T}$. Then $|S_{Ti}|\leq w(p_{T}^{T})$.

###### Proof.

As before, assume WLOG that $p(y_{i})=p_{1}^{T}$.

######  Case 1.

$w(y_{i})>w(p_{1}^{T})$.

We know from the proof of Claim 1, Case 1 that this implies
$|S_{Ti}|<w(p_{1}^{T})$. We have

$\displaystyle|S_{Ti}|\cdot d(p_{T}^{T},y_{i})$ $\displaystyle=\sum_{p\in
S_{Ti}}d(y_{i},p_{T}^{T})$ $\displaystyle\leq\sum_{p\in
S_{Ti}}d(p,p_{T}^{T})+\sum_{p\in S_{Ti}}d(p,y_{i})$
$\displaystyle\leq(\beta_{T+1}+2)\textsf{OPT}+2\textsf{OPT}$ (Claim 1)
$\displaystyle\leq 2\beta_{T+1}\cdot\textsf{OPT}$ $\displaystyle\leq
w(p_{T}^{T})\cdot d(p_{T}^{T},y_{i})$

where in the last line we have applied Proposition 5, using that
$w(y_{i})>w(p_{1}^{T})$, Observation 2, and $p_{1}^{T}$ and $p_{T}^{T}$ are
$\beta_{T}$-well-separated w.r.t. $w$. Finally, dividing both ends of the
chain of inequalities by $d(p_{T}^{T},y_{j})$ gives $|S_{Tj}|\leq
w(p_{T}^{T})$, as desired.

######  Case 2.

$w(y_{i})\leq w(p_{1}^{T})$.

First consider when $w(p_{T}^{T})\geq w(y_{i})$. Then $w(p_{T}^{T})\geq
w(y_{i})\geq m(y_{i})\geq|S_{Ti}|$, so the claim follows.

So the last case to consider is when $w(p_{T}^{T})<w(y_{i})$. It suffices to
show that $w(p_{T}^{T})\cdot d(p_{T}^{T},y_{i})\geq
2\beta_{T+1}\cdot\textsf{OPT}$; then, we can just apply the argument in Case
1. Suppose to the contrary that $w(p_{T}^{T})\cdot
d(p_{T}^{T},y_{i})<2\beta_{T+1}\cdot\textsf{OPT}$. Then

$\displaystyle\beta_{T}\cdot\textsf{OPT}$ $\displaystyle\leq w(p_{T}^{T})\cdot
d(p_{T}^{T},p_{1}^{T})$ $\displaystyle\leq w(p_{T}^{T})\cdot
d(p_{T}^{T},y_{i})+w(p_{T}^{T})\cdot d(y_{i},p_{1}^{T})$ $\displaystyle\leq
2\beta_{T+1}\cdot\textsf{OPT}+w(p_{T}^{T})\cdot d(y_{i},p_{1}^{T})$
$\displaystyle<2\beta_{t+1}\cdot\textsf{OPT}+w(y_{i})\cdot d(y_{i},p_{1}^{T})$
$\displaystyle<2\beta_{T+1}\cdot\textsf{OPT}+\beta_{T+1}\cdot\textsf{OPT}$
$\displaystyle=\beta_{T}\cdot\textsf{OPT}$

where the second-to-last line follows from Observation 2. The left-hand and
right-hand sides give a contradiction, concluding the proof of the case and
the claim. ∎

######  Claim 4.

$cost(S_{far,T};p_{T}^{T})\leq k\cdot(\beta_{T+1}+2)\textsf{OPT}$ and
$|S_{far,T}|\leq k\cdot w(p_{T}^{T})$.

###### Proof.

By Claims 1 and 2,

$cost(S_{far,T};p_{T}^{T})=\sum_{i:p(y_{i})\neq
p_{T}^{T}}cost(S_{Ti};p_{T}^{T})\leq k\cdot(\beta_{T+1}+2)\textsf{OPT}$

By Claim 3,

$|S_{far,T}|=\sum_{i:p(y_{i})\neq p_{T}^{T}}|S_{Ti}|\leq k\cdot w(p_{T}^{T}).$

∎

∎

The proof of Lemma 4 can be found in Appendix D. The argument is by induction
and is similar in flavor to the proof of Lemma 5, which we give below. Lemma 5
implies Theorem 2.

###### Proof of Lemma 5.

The proof is by induction. Let $C_{j}$, $S_{ji}$, and $S_{far,j}$ be as in
Lemma 3. Define $S_{near,j}=\bigcup_{i:p(y_{i})=p_{j}^{T}}S_{ji}$ and $S_{j}$
to be the elements in $C_{j}$ that are assigned to $p_{j}^{T}$ in the
clustering of $X(T)\setminus X(T^{-})$ induced by $P_{T}$. Let $w^{t}$ denote
the natural weights at the end of phase $t$. First we need the following key
claim.

######  Claim 1.

For any
$x,y\in\delta^{+}(p_{j}^{T})\cup\delta^{-}(p_{j}^{T})\cup\\{p_{j}^{T}\\}$, $x$
and $y$ are $2\beta_{T+1}$-attached w.r.t. $w^{T}$.

###### Proof of Claim 1.

If $x$ or $y$ is $p_{j}^{T}$, then the claim automatically holds by
Proposition 2. There are two other cases. The first case is, WLOG,
$x\in\delta^{-}(p_{j}^{T})$. Regardless of whether $y$ is in
$\delta^{-}(p_{j}^{T})$ or $\delta^{+}(p_{j}^{T})$, the claim holds by
Propositions 2 and 5. The second case is that $x,y\in\delta^{+}(p_{j}^{T})$.
We prove the stronger statement that $x$ and $y$ are $\beta_{T+1}$-attached
w.r.t. $w^{T}$. Suppose to the contrary that $x$ and $y$ are
$\beta_{T+1}$-well-separated. We claim that this implies

$\\{p_{1}^{T},\dots,p_{T}^{T}\\}\cup\\{x,y\\}\setminus\\{p_{j}^{T}\\}$ (1)

is $\beta_{T+1}$-well-separated w.r.t. $w^{T}$; this would give a
contradiction, since if an Exchange Operation were available, it would have
been executed. Now suppose that (1) does not hold. Then WLOG
$p_{j^{\prime}}^{T}$ and $x$ are $\beta_{T+1}$-attached w.r.t. $w^{T}$, for
some $j^{\prime}\neq j$. Since $x\in\delta^{+}(p_{j}^{T})$ and since $x$ and
$p_{j}^{T}$ are $\beta_{T+1}$-attached w.r.t. $w^{T}$, by Proposition 5,
$p_{j}^{T}$ and $p_{j^{\prime}}^{T}$ are $2\beta_{T+1}$-attached w.r.t.
$w^{T}$. This contradicts that $p_{j}^{T}$ and $p_{j^{\prime}}^{T}$ are
$\beta_{T}$-well-separated w.r.t. $w^{T}$, since $2\beta_{T+1}<\beta_{T}$.
This concludes the proof of the case and the claim. ∎

To bound the cost contribution of $C_{j}^{T^{-}}$, we case on which statement
holds in Lemma 2.

######  Case 1.

$c_{j}^{T^{-}}$ is $\beta_{T+1}$-attached to $p_{j}^{T}$ w.r.t. $w^{T}$ (i.e.,
(b) holds in Lemma 2).

Since in Case 1, $c_{j}^{T^{-}}$ is $\beta_{T+1}$-attached to $p_{j}^{T}$
w.r.t. $w^{T}$,
$c_{j}^{T^{-}}\in\delta^{+}(p_{j}^{T})\cup\delta^{-}(p_{j}^{T})$. Also,
$c_{j}^{T}$ by definition is in $\delta^{+}(p_{j}^{T})\cup\\{p_{j}^{T}\\}$. So
by Claim 1, $c_{j}^{T^{-}}$ is $2\beta_{T+1}$-attached to $c_{j}^{T}$ w.r.t.
$w^{T}$. Using this, we bound $cost(C_{j}^{T^{-}};c_{j}^{T})$:

$\displaystyle cost(C_{j}^{T^{-}};c_{j}^{T})$ $\displaystyle\leq
cost(C_{j}^{T^{-}};c_{j}^{T^{-}})+|C_{j}^{T^{-}}|\cdot
d(c_{j}^{T^{-}},c_{j}^{T})$ $\displaystyle\leq
g(T^{-},k)\cdot\textsf{OPT}+|C_{j}^{T^{-}}|\cdot d(c_{j}^{T^{-}},c_{j}^{T})$
$\displaystyle\leq g(T^{-},k)\cdot\textsf{OPT}+(2k+1)\cdot T^{-}\cdot
w^{T^{-}}(c_{j}^{T^{-}})\cdot d(c_{j}^{T^{-}},c_{j}^{T})$ $\displaystyle\leq
g(T^{-},k)\cdot\textsf{OPT}+(2k+1)\cdot T^{-}\cdot w^{T}(c_{j}^{T^{-}})\cdot
d(c_{j}^{T^{-}},c_{j}^{T})$ $\displaystyle\leq
g(T^{-},k)\cdot\textsf{OPT}+(2k+1)\cdot T^{-}\cdot
2\beta_{T+1}\cdot\textsf{OPT}$ (2)

where the third inequality is due to Lemma 4.

######  Case 2.

(b) does not hold in Lemma 2, so (a) holds, i.e.,
$w^{T^{-}}(c_{j}^{T^{-}})\leq w^{T}(p_{j}^{T})$ and
$w^{T^{-}}(c_{j}^{T^{-}})\cdot
d(c_{j}^{T^{-}},p_{j}^{T})\leq\beta_{T^{-}}(T-T^{-})\cdot\textsf{OPT}$.

We bound $cost(C_{j}^{T^{-}};c_{j}^{T})$:

$\displaystyle cost(C_{j}^{T^{-}};c_{j}^{T})$ $\displaystyle\leq
cost(C_{j}^{T^{-}};c_{j}^{T^{-}})+|C_{j}^{T^{-}}|\cdot
d(c_{j}^{T^{-}},c_{j}^{T})$ $\displaystyle\leq
g(T^{-},k)\cdot\textsf{OPT}+|C_{j}^{T^{-}}|\cdot
d(c_{j}^{T^{-}},p_{j}^{T})+|C_{j}^{T^{-}}|\cdot d(p_{j}^{T},c_{j}^{T})$ (3)

and now we use the assumptions of the case to continue bounding from (3):

$\displaystyle|C_{j}^{T^{-}}|\cdot d(c_{j}^{T^{-}},p_{j}^{T})$
$\displaystyle\leq(2k+1)\cdot T^{-}\cdot w^{T^{-}}(c_{j}^{T^{-}})\cdot
d(c_{j}^{T^{-}},p_{j}^{T})$ $\displaystyle\leq(2k+1)\cdot
T^{-}\cdot\beta_{T^{-}}(T-T^{-})\cdot\textsf{OPT}$ (4)

where the first inequality is due to Lemma 4. Next,

$\displaystyle|C_{j}^{T^{-}}|\cdot d(p_{j}^{T},c_{j}^{T})\leq(2k+1)T^{-}\cdot
w^{T^{-}}(c_{j}^{T^{-}})\cdot d(p_{j}^{T},c_{j}^{T})$
$\displaystyle\leq(2k+1)T^{-}\cdot w^{T}(p_{j}^{T})\cdot
d(p_{j}^{T},c_{j}^{T})$
$\displaystyle\leq(2k+1)T^{-}\cdot\beta_{T+1}\cdot\textsf{OPT}$ (5)

where the first inequality is due to Lemma 4 and the last inequality is due to
Proposition 3. So combining (3), (4), (5) gives

$cost(C_{j}^{T^{-}};c_{j}^{T})\leq g(T^{-},k)\cdot\textsf{OPT}+(2k+1)\cdot
T^{-}\cdot(\beta_{T^{-}}(T-T^{-})+\beta_{T+1})\cdot\textsf{OPT}.$ (6)

Now we have bounds (2) and (6) for $cost(C_{j}^{T^{-}};c_{j}^{T})$. Recall
that $C_{j}^{T}=C_{j}^{T^{-}}\cup S_{far,j}\cup S_{near,j}\cup S_{j}$. The
following bounds will hold regardless of whether we are in Case 1 or 2. We
have

$cost(S_{j};c_{j}^{T})\leq cost(S_{j};p_{j}^{T})+|S_{j}|\cdot
d(p_{j}^{T},c_{j}^{T})\leq 2\textsf{OPT}+w^{T}(p_{j}^{T})\cdot
d(p_{j}^{T},c_{j}^{T})\leq(2+\beta_{T+1})\textsf{OPT}$ (7) $\displaystyle
cost(S_{near,j};c_{j}^{T})$
$\displaystyle=\sum_{i:p(y_{i})=p_{j}^{T}}cost(S_{ji};c_{j}^{T})\leq\sum_{i:p(y_{i})=p_{j}^{T}}\sum_{p\in
S_{ji}}d(p,c_{j}^{T})$ $\displaystyle\leq
2\textsf{OPT}+\sum_{i:p(y_{i})=p_{j}^{T}}w^{T}(y_{i})\cdot
d(y_{i},c_{j}^{T})\leq(2k\beta_{T+1}+2)\textsf{OPT}$ (8)

where we have used Claim 1 and that $|S_{ji}|\leq w^{T}(y_{i})$. Finally, by
Lemma 3,

$\displaystyle cost(S_{far,j};c_{j}^{T})\leq
cost(S_{far,j};p_{j}^{T})+|S_{far,j}|\cdot d(p_{j}^{T},c_{j}^{T})\leq
k(2\beta_{T+1}+2)\textsf{OPT}$ (9)

Combining (7), (8), (9) with (2) or (6) gives the sought bound:

$cost(C_{j}^{T};c_{j}^{T})\leq[g(T^{-},k)+g(k)]\textsf{OPT}\leq
g(T,k)\cdot\textsf{OPT}.$

∎

## References

  * [1] Vijay Arya et al.  “Local Search Heuristics for k-Median and Facility Location Problems”  In _SIAM Journal of Computing_ 33.3, 2004, pp. 544–562
  * [2] Christopher M. Bishop  “Pattern Recognition and Machine Learning”  Berlin, Heidelberg: Springer-Verlag, 2006
  * [3] Jaroslaw Byrka et al.  “An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization”  In _ACM Transactions on Algorithms_ 13.2, 2017, pp. 23:1–23:31
  * [4] T-H. Hubert Chan, Arnaud Guerqin and Mauro Sozio  “Fully Dynamic K-Center Clustering”  In _World Wide Web Conference_ , 2018, pp. 579–587
  * [5] Moses Charikar, Sudipto Guha, Éva Tardos and David B. Shmoys  “A Constant-Factor Approximation Algorithm for the k-Median Problem”  In _Journal of Computer and Systems Sciences_ 65.1, 2002, pp. 129–149
  * [6] Moses Charikar, Chandra Chekuri, Tomás Feder and Rajeev Motwani  “Incremental Clustering and Dynamic Information Retrieval”  In _SIAM Journal of Computing_ 33.6, 2004, pp. 1417–1440
  * [7] Vincent Cohen-Addad et al.  “Fully Dynamic Consistent Facility Location”  In _Conference on Neural Information Processing Systems_ , 2019, pp. 3250–3260
  * [8] Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard and Ola Svensson  “Consistent k-Clustering for General Metrics”  In _ACM-SIAM Symposium on Discrete Algorithms_ , 2021
  * [9] Xiangyu Guo, Janardhan Kulkarni, Shi Li and Jiayi Xian  “Consistent k-Median: Simpler, Better and Robust”  In _International Conference on Artificial Intelligence and Statistics_ 130, 2021, pp. 1135–1143
  * [10] K. Jain and V. V. Vazirani  “Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation”  In _Journal of the ACM_ 48.2, 2001, pp. 274 –296
  * [11] Silvio Lattanzi and Sergei Vassilvitskii  “Consistent k-Clustering”  In _International Conference on Machine Learning_ , 2017, pp. 1975–1984
  * [12] Shi Li and Ola Svensson  “Approximating k-Median via Pseudo-Approximation”  In _SIAM Journal of Computing_ 45.2, 2016, pp. 530–547
  * [13] Edo Liberty, Ram Sriharsha and Maxim Sviridenko  “An algorithm for online k-means clustering”  In _Workshop on Algorithm Engineering and Experiments_ , 2016, pp. 81–89
  * [14] Edo Liberty, Ram Sriharsha and Maxim Sviridenko  “k-means clustering” talk slides, https://www.cs.yale.edu/homes/el327/papers/OnlineKMeansAlenexEdoLiberty.pdf
  * [15] A. Meyerson  “Online Facility Location”  In _IEEE Symposium on Foundations of Computer Science_ , 2001, pp. 426–431
  * [16] Adam Meyerson, Liadan O’Callaghan and Serge Plotkin  “A k-median algorithm with running time independent of data size”  In _Machine Learning_ 56.1 Springer, 2004, pp. 61–87
  * [17] Tim Roughgarden  “Beyond the Worst-Case Analysis of Algorithms”  Cambridge University Press, 2021

##  Appendix A Helper Propositions

######  Fact 1 (Fact 2.1 in [16]).

Let $N$ be a set of points, with $S\subseteq N$. Let $k$ be an integer with
$0\leq k\leq n$. Let $K\subseteq S$ be the $k$-element subset of $S$
minimizing $\sum_{x\in S}d(x,K)$ where $d(\cdot,\cdot)$ is the distance
function on $N$, and $d(x,K)$ denotes $\min_{m\in K}d(x,m)$. Then if
$K^{\prime}$ is a $k$-element subset of $N$, $\sum_{x\in S}d(x,K)\leq
2\sum_{x\in S}d(x,K^{\prime})$.

######  Proposition 5.

Let $x,y,p$ be three points, and let $w$ denote some associated weights.
Assume that $\beta,\beta_{x},\beta_{y},\textsf{OPT}>0$. Suppose that $w(x)\leq
w(p)$ and that $x$ and $y$ are $(\beta,\textsf{OPT})$-well-separated w.r.t.
$w$. If $x$ and $p$ are $(\beta_{x},\textsf{OPT})$-attached w.r.t. $w$, and
$y$ and $p$ are $(\beta_{y},\textsf{OPT})$-attached w.r.t. $w$, then
$\beta<\beta_{x}+\beta_{y}$.

###### Proof of Proposition 5.

We consider two cases. First, suppose that $w(p)\leq w(y)$. Then

$\displaystyle\beta\cdot\textsf{OPT}$ $\displaystyle\leq w(x)\cdot d(x,y)$
$\displaystyle\leq w(x)\cdot d(x,p)+w(x)\cdot d(p,y)$ $\displaystyle\leq
w(x)\cdot d(x,p)+w(p)\cdot d(p,y)$
$\displaystyle<\beta_{x}\cdot\textsf{OPT}+\beta_{y}\cdot\textsf{OPT}.$

For the second case, $w(y)\leq w(p)$. Then

$\displaystyle\beta\cdot\textsf{OPT}$
$\displaystyle\leq\min\\{w(x),w(y)\\}\cdot d(x,y)$
$\displaystyle\leq\min\\{w(x),w(y)\\}\cdot d(x,p)+\min\\{w(x),w(y)\\}\cdot
d(y,p)$ $\displaystyle\leq w(x)\cdot d(x,p)+w(y)\cdot d(y,p)$
$\displaystyle<\beta_{x}\cdot\textsf{OPT}+\beta_{y}\cdot\textsf{OPT}.$

∎

##  Appendix B Lower Bound

###### Proof of Theorem 1.

For sake of contradiction, assume there is an online algorithm $A$ that is a
$c$-approximation for $c\leq\frac{k-1}{2}-\epsilon$ and any $\epsilon>0$. The
algorithm is given a budget OPT. The sequence of points that arrives will lie
in $\mathbb{R}^{k}$. First there are $10k^{2}$ points $P_{0}$ that arrive at
location $(0,0,\dots,0)$. We may assume that $A$ assigns each of these the
same label.

There are $k-1$ remaining phases for how points are released. Index these
phases as $1,2,\ldots k-1$. At the end of the $i$th phase, $A$ will have
accumulated cost at least $\frac{i}{2}\textsf{OPT}$. In the end, $A$’s cost
will be at least $\frac{k-1}{2}\textsf{OPT}$, contradicting the assumption
that $A$ is a $c$-approximation. Additionally, by the end of the $i$th phase,
the algorithm will have used at least $i+1$ labels. All points in the $i$th
phase will arrive at location $(0,0,\ldots\textsf{OPT},\ldots 0)$ where the
$i$th dimension is non-zero. The number of points that arrive will be
$10k^{2}$ at this location. The majority of these points will have to be
labelled with a single label by the algorithm.

Consider phase $i$. The adversary releases one point $q_{i}$ at location
$(0,0,\ldots\textsf{OPT},\ldots 0)$. First _assume_ the algorithm the
algorithm does not give this point a new label. We will revisit this
assumption at the end of the proof. Then regardless of what label the
algorithm gives this point, it is distance at least OPT from all other points
that have arrived. Thus, this point will add an additional $\textsf{OPT}/2$
cost to the algorithm. Inductively, the total algorithm cost is at least
$\frac{i}{2}\textsf{OPT}$.

Next $10k^{2}-1$ points arrive at this same location. If the algorithm does
not label half of these points with a new label, then these points will be
grouped with points that arrived previously. Since prior points are distances
at least OPT away, this will make the algorithm’s total cost larger than
$\Omega(k^{2}\textsf{OPT})$. Thus, the algorithm must label half of these
points with a new label. Now the inductive invariants are satisfied.

At the end, the optimal solution labels the points that arrive in each phases
a different label. The total optimal cost is $0$ and the algorithm has cost
$\Omega(k\textsf{OPT})$.

Now we revisit the assumption that $q_{i}$ must not be given a new label by
$A$. Indeed, say it is given a new label. Then the above procedure terminates
at this time. Instead, we know the algorithm has used $i+1$ labels. There is a
clustering of the points that have arrived whose cost is below OPT and only
uses $i$ labels. Intuitively, this is a large mistake.

Indeed, consider the following. There will be $k-i$ points $P^{*}$ that will
arrive. The $\ell$th point arrives at location $(0,0,\ldots
L\cdot\textsf{OPT},\ldots 0)$ where $L$ is a parameter. Here $\ell\in[k-i]$.
The non-zero dimension is the $(i+\ell)th$ dimension.

The optimal solution labels $q_{i}$ the same label as the points in $P_{0}$
and this cluster has cost OPT. All other points get a unique label depending
on which dimension is non-zero. $k-1$ dimensions are used, combined with
$P_{0}$ this is $k$ labels. The cost of these points are $0$ and the only cost
is $q_{i}$ paying cost OPT. The optimal cost is bounded.

On the other hand, $A$ only has $k-i-1$ unused labels when points in $P^{*}$
begin arriving. One of them must be given a label as some other point whose
distance is at least $L\textsf{OPT}$ away. The cost of this cluster is at
least $\frac{L}{2}\textsf{OPT}$. Setting $L$ large, contradicts the bounded
approximation ratio of $A$.

∎

##  Appendix C Omitted Proofs from Section 5.3

###### Proof of Proposition 3.

By the definition ($\ddagger$ ‣ 4.1) of $c_{j}^{T}$, we know that
$c_{j}^{T}\in\delta^{+}(p_{j}^{T})\cup p_{j}^{T}\subseteq\\\
\\{y_{1},\dots,y_{l},p_{j}^{T},c_{j}^{T^{-}}\\}$. By Proposition 2 and the
fact that $c_{j}^{T^{-}}\in\delta^{+}(p_{j}^{T})$ only if $c_{j}^{T^{-}}$ is
$\beta_{T+1}$-attached to $p_{j}^{T}$ w.r.t. $w^{T}$, $c_{j}^{T}$ is
$\beta_{T+1}$-attached to $p_{j}^{T}$ w.r.t. $w^{T}$. That
$w^{T}(c_{j}^{T})\geq w^{T}(p_{j}^{T})$ follows directly from $c_{j}^{T}$
maximizing $w^{T}$ over a set that includes $p_{j}^{T}$, and this is with
equality if and only if $c_{j}^{T}=p_{j}^{T}$ due to the tiebraking rule in
the definition ($\ddagger$ ‣ 4.1) of estimated center. ∎

###### Proof of Lemma 1.

The proof will consist of an inner induction nested in an outer induction. Let
$1=T_{1}<T_{2}<\cdots<T_{L}\leq k$ denote the non-intermediate phases (i.e.,
phases during which at least one point receives a label). Take $T=T_{i}$, so
that $T^{+}=T_{i+1}$. In the outer induction, we will prove Lemma 1 for the
non-intermediate phases: i.e., if $p_{1}^{T},\dots,p_{T}^{T}$ are
$\beta_{T}$-well-separated w.r.t. the natural weights at the start of phase
$T$, then $p_{1}^{T^{+}},\dots,p_{T^{+}}^{T^{+}}$ are $\beta_{T^{+}}$-well-
separated w.r.t. the natural weights at the start of phase $T^{+}$. Note the
base case is satisfied, since $\\{p_{1}^{1}\\}$ is trivially a
$\beta_{1}$-well-separated set w.r.t. the natural weights at the start of
phase 1, thus also w.r.t. the natural weights at the end of phase 1. Given the
inductive assumption that $p_{1}^{T},\cdots,p_{T}^{T}$ are $\beta_{T}$-well-
separated w.r.t. the natural weights at the start of phase $T$, we prove the
following claim. Taking $t=T^{+}$ in the claim completes the proof.

See 4

Note that if (a) holds, another Add Operation is available, so $t<T^{+}$.

The proof of Proposition 4 will be the inner induction. The first part
($\Diamond$ ‣ 4) of the claim establishes that Lemma 1 holds for the
intermediate phases. Note that while we only need to prove ($\Diamond$ ‣ 4) to
establish Lemma 1, we will need to couple the inner induction with the second
part of the claim to actually prove ($\Diamond$ ‣ 4). The second part of the
claim states that, upon the arrival of the single point $x_{i}$, as we
consecutively reset the pivots until no Add Operation or Exchange Operation is
available, the (fixed) estimated center $c_{j}^{T}$ for cluster $j$ at the end
of phase $T$ remains attached to the pivot for label $j$ — even though the
well-separation parameter $\beta_{t}$ decreases and the pivot for label $j$
may change position.

###### Proof of Proposition 4.

The proof is by induction. First we prove the base case $t=T$. We know that
$p_{1}^{T},\dots,p_{T}^{T}$ are $\beta_{T}$-well-separated w.r.t. the weights
at the start of phase $T$ by the inductive assumption of the outer induction,
thus also w.r.t. $w_{i-1}$. So ($\Diamond$ ‣ 4) is satisfied. Also, we know
that $c_{j}^{T}$ is $\beta_{T+1}$-attached to $p_{j}^{T}$ w.r.t. $w_{i-1}$ by
Proposition 3, so (b) is satisfied. This concludes the base case.

Next we assume the claim holds for $t\in[T,T^{+})$. The inductive step is to
prove that the claim holds for $t+1$, or when this phase is skipped as in Case
4 of the Add Operation and Case 5 of the Exchange Operation, holds for $t+2$.

#### Inductive step for ($\Diamond$ ‣ 4).

We start by proving the inductive step for the first part ($\Diamond$ ‣ 4) of
the claim for $t+1$ or $t+2$. If one of Cases 1 through 3 of the Add Operation
is executed, then ($\Diamond$ ‣ 4) holds by construction for $t+1$. This is
because in these cases the new pivot location ($x_{\alpha}$ or some
$c_{j}^{T}$, $j\in[T]$) is $\beta_{t+1}$-well-separated from
$p_{1}^{t},\cdots,p_{t}^{t}$ w.r.t. $w_{i}=w_{t+1}$. Likewise, if one of Cases
1 through 4 of the Exchange Operation is executed, then ($\Diamond$ ‣ 4) holds
by construction for $t+1$. This is because in these cases the new set of
pivots is
$\\{p_{1}^{t},\cdots,p_{t}^{t}\\}\cup\\{x_{\alpha},x_{\gamma}\\}\setminus\\{p_{j}^{t}\\}$,
which is $\beta_{t+1}$-well-separated w.r.t. $w_{i}=w_{t+1}$. So it remains to
show that ($\Diamond$ ‣ 4) holds for $t+2$ in Case 4 of the Add Operation and
Case 5 of the Exchange Operation.

######  Case 1.

Case 4 of the Add Operation is executed.

In particular, we need to show that (A) $c_{f}^{T}$ and $c_{g}^{T}$ are
$\beta_{t+2}$-well-separated w.r.t. $w_{t+2}=w_{i}$, and (B) $c_{f}^{T}$ and
$c_{g}^{T}$ are each $\beta_{t+2}$-well-separated from
$p_{1}^{t},\dots,p_{t}^{t}$ w.r.t. $w_{t+2}=w_{i}$.

First we prove (A). Suppose to the contrary that $c_{f}^{T}$ and $c_{g}^{T}$
are $\beta_{t+2}$-attached w.r.t. $w_{i}$. Then $c_{f}^{T}$ and $c_{g}^{T}$
are $\beta_{t+2}$-attached w.r.t. $w_{i-1}$, since $w_{i-1}\leq w_{i}$ holds
pointwise. Also, by Proposition 3, $c_{f}^{T}$ is $\beta_{T+1}$-attached to
$p_{f}^{T}$ w.r.t. $w_{i-1}$ and $w_{i-1}(c_{f}^{T})\geq w_{i-1}(p_{f}^{T})$
(and likewise for $c_{g}^{T},p_{g}^{T}$). Since by the base case
$p_{1}^{T},\cdots,p_{T}^{T}$ are $\beta_{T}$-well-separated w.r.t. $w_{i-1}$,
and $\beta_{t+2}+\beta_{T+1}+\beta_{T+1}<\beta_{T}$, we reach a contradiction
through two applications of Proposition 5. We conclude that $c_{f}^{T}$ and
$c_{g}^{T}$ are $\beta_{t+2}$-well-separated w.r.t. $w_{t+2}=w_{i}$.

Next we prove (B). WLOG, we will first show that $c_{f}^{T}$ is
$\beta_{t+2}$-well-separated from $p_{f}^{t}$ w.r.t. $w_{t+2}=w_{i}$. First,
we show that $w_{i}(c_{f}^{T})\geq w_{i}(p_{f}^{t})$. This is clearly true for
$t>T$, by assumption of Case 4 of the Add Operation and the fact that
$w_{t}=w_{i}$. When $t=T$, the argument is more subtle. Note that
$c_{f}^{T}\neq p_{f}^{t}$, since $c_{f}^{T}$ is $\beta_{t+2}$-attached to
$x_{\alpha}$ w.r.t. $w_{i}$, while $x_{\alpha}$ is $\beta_{t+1}$-well-
separated from $p_{f}^{t}$ w.r.t. $w_{i}$. In turn, since $c_{f}^{T}\neq
p_{f}^{t}$ if $t=T$, by Proposition 3 we have
$w_{i-1}(c_{f}^{T})>w_{i-1}(p_{f}^{t})$. Since the natural weights can only go
up by 1 on the arrival of $x_{i}$, this means that $w_{i}(c_{f}^{T})\geq
w_{i}(p_{f}^{t})$ if $t=T$. So we conclude $w_{i}(c_{f}^{T})\geq
w_{i}(p_{f}^{t})$ for all $t\in[T,T^{+})$ as desired. Thus, by Proposition 5,
it is not possible for $c_{f}^{T}$ to be $\beta_{t+2}$-attached to $p_{f}^{t}$
w.r.t. $w_{i}$, since $w_{i}(c_{f}^{T})\geq w_{i}(p_{f}^{t})$, $c_{f}^{T}$ is
$\beta_{t+2}$-attached to $x_{\alpha}$ w.r.t. $w_{i}$ (by definition of Case 4
of the Add Operation), and $p_{f}^{t}$ and $x_{\alpha}$ are
$\beta_{t+1}$-well-separated w.rt. $w_{i}$ (by definition of the Add
Operation).

To finish the proof of (B), we need to show that $c_{f}^{T}$ is
$\beta_{t+2}$-well-separated from $p_{l}^{t}$ w.r.t. $w_{t+2}$,
$l\in[t]\setminus f$. By the inductive assumption, at least one of statements
(a)—(c) in the statement of the proposition holds. Note that (a) in the
statement of the proposition does not hold, for else Case 1 of the Add
Operation would have been executed. Also (c) in the statement of the
proposition does not hold, since by assumption of Case 4 of the Add Operation,
$w_{t}(c_{f}^{T})\geq w_{t}(p_{f}^{t})$. So (b) in the statement of the claim
holds, i.e., $c_{f}^{T}$ is $\beta_{t+1}$-attached to $p_{f}^{t}$ w.r.t.
$w_{t}$. Also by the inductive assumption, $p_{f}^{t}$ and $p_{l}^{t}$ are
$\beta_{t}$-well-separated w.r.t. $w_{t}$. Since
$\beta_{t+1}+\beta_{t+2}<\beta_{t}$, it must be the case by Proposition 5 that
$c_{f}^{T}$ and $p_{l}^{t}$ are $\beta_{t+2}$-well-separated w.r.t. $w_{t}$
for $l\neq f$. Thus $c_{f}^{T}$ and $p_{l}^{t}$ are $\beta_{t+2}$-well-
separated w.r.t. $w_{t+2}$ as well, concluding the proof of (B) and of Case 1.

######  Case 2.

Case 5 of the Exchange Operation is executed.

First note that $\\{x_{\alpha},x_{\gamma}\\}\cup\\{p_{l}^{t}\mid
l\in[t]\setminus j\\}$ is $\beta_{t+1}$-well-separated w.r.t. $w_{t+2}=w_{i}$
by assumption of the Exchange Operation, thus this set is also
$\beta_{t+2}$-well-separated w.r.t. $w_{i}$.

Next, we need to show that $c_{j}^{T}$ is $\beta_{t+2}$-well-separated from
$\\{p_{l}^{t}\mid l\in[t]\setminus j\\}\cup\\{x_{\alpha},x_{\gamma}\\}$ w.r.t.
$w_{i}$. Since Cases 3 and 4 of the Exchange Operation were not executed,
$c_{j}^{T}$ is $\beta_{t+2}$-well-separated from $x_{\alpha}$ and from
$x_{\gamma}$ w.r.t. $w_{i}$.

Next, note that since an Add Operation, which takes precedence over an
Exchange Operation, was not executed, (a) in the statement of the proposition
cannot hold in the inductive assumption for $j$. Moreover, since Case 2 of the
Exchange Operation is not executed and (c) in the statement of the proposition
cannot hold when $t=T$ (by Proposition 3), (c) in the statement of the
proposition cannot hold in the inductive assumption for $j$. We conclude
$c_{j}^{T}$ is $\beta_{t+1}$-attached to $p_{j}^{t}$ w.r.t. $w_{t}$ and
$w_{t}(c_{j}^{T})\geq w_{t}(p_{j}^{t})$. This implies by Proposition 5 that
$c_{j}^{T}$ is $\beta_{t+2}$-well-separated from $p_{l}^{t}$ w.r.t. $w_{t}$
for $l\neq j$, since $p_{j}^{t}$ and $p_{l}^{t}$ are $\beta_{t}$-well-
separated w.r.t. $w_{t}$ by the inductive assumption. Hence $c_{j}^{T}$ is
$\beta_{t+2}$-well-separated from $p_{l}^{t}$ w.r.t. $w_{t+1}=w_{i}$ for
$l\in[t]\setminus j$.

#### Inductive step for (a)—(c).

Next we prove the inductive step holding for the second part of the
proposition. We first introduce the following fact which we will use
repeatedly in the rest of the proof.

######  Fact 2.

Let $j,j^{\prime}\in[T]$, $j\neq j^{\prime}$. Then $c_{j}^{T}$ and
$c_{j^{\prime}}^{T}$ are $\beta_{T+1}$-well-separated w.r.t. $w_{i-1}$.

###### Proof of Fact 2.

Suppose to the contrary that $c_{j}^{T}$ and $c_{j^{\prime}}^{T}$ are
$\beta_{T+1}$-attached w.r.t. $w_{i-1}$. We also know by Proposition 3 that
$c_{j}^{T},c_{j^{\prime}}^{T}$ are $\beta_{T+1}$-attached to
$p_{j}^{T},p_{j^{\prime}}^{T}$, respectively, w.r.t. $w_{i-1}$, and that
$w_{i-1}(c_{j}^{T})\geq w_{i-1}(p_{j}^{T})$ and
$w_{i-1}(c_{j^{\prime}}^{T})\geq w_{i-1}(p_{j^{\prime}}^{T})$. By the base
case of the inner induction, $p_{1}^{T},\cdots,p_{T}^{T}$ are
$\beta_{T}$-well-separated w.r.t. $w_{i-1}$, so applying Proposition 5 gives a
contradiction. ∎

In the remainder of the proof, we need to show that, given the inductive
assumption that Proposition 4 holds for $t$, we have that at least one of
statements (a)–(c) holds for $t+1$ (or when this phase is skipped, $t+2$).
(Recall we already proved the first part of the inductive step, i.e.,
($\Diamond$ ‣ 4) holds for $t+1$.)

We case on which operation is executed to generate the new set of $t+1$ (or
$t+2$) pivots from $p_{1}^{t},\dots,p_{t}^{t}$, and on which of statements
(a)–(c) holds in the inductive assumption for $t$.

######  Case 1.

Case 1 of the Add Operation is executed.

Let $j^{*}$ be the specific $j$ chosen in Case 1 of the Add Operation. We need
to show that for every $j\in[T]$, at least one of statements (a)–(c) holds for
$t+1$.
If $j=j^{*}$, then $p_{j}^{t+1}=c_{j}^{T}$, so certainly $c_{j}^{T}$ is
$\beta_{t+2}$-attached to $p_{j}^{t+1}$ w.r.t. $w_{t+1}$, so statement (b) is
satisfied for $t+1$.
Now we consider $j\neq j^{*}$. We case on which of statements (a)–(c) holds
for $j\in[T]$ in the inductive assumption for $t$.

If statement (a) holds in the inductive assumption for $t$. Then by
definition, $c_{j}^{T}$ is $\beta_{t+1}$-well-separated from
$p_{1}^{t},\dots,p_{t}^{t}$ w.r.t. $w_{i}$, so it must also be
$\beta_{t+2}$-well-separated from $p_{1}^{t},\dots,p_{t}^{t}$ w.r.t. $w_{i}$.
Moreover, by Fact 2, $c_{j}^{T}$ is $\beta_{T+1}$-well-separated (thus
$\beta_{t+2}$-well-separated) from $p_{j^{*}}^{t+1}=c_{j^{*}}^{T}$ w.r.t.
$w_{i-1}$, thus also w.r.t. $w_{i}$. Since
$\\{p_{1}^{t+1},\dots,p_{t+1}^{t+1}\\}=\\{p_{1}^{t},\dots,p_{t}^{t},c_{j^{*}}^{T}\\}$,
statement (a) holds for $c_{j}^{T}$ and the inductive step $t+1$ is satisfied.

Else if statement (c) holds in the inductive assumption for $t$. Note that
$p_{j}^{t}=p_{j}^{t+1}$ for $j\neq j^{*}$ when Case 1 is executed. Moreover,
if statement (c) holds, it must be the case that $t>T$, since
$w_{i-1}(c_{j}^{T})\geq w_{i-1}(p_{j}^{T})$ by construction. But if $t>T$,
then $w_{t+1}=w_{t}=w_{i}$. Also, $f(t+1,T)>f(t,T)$. So statement (c) still
holds for $t+1$.

Else statement (b) holds in the inductive assumption for $t$. In this case,
since statement (c) does not hold, then $c_{j}^{T}$ is $\beta_{t+1}$-attached
to $p_{j}^{t}$ w.r.t. $w_{t}$, and $w_{t}(c_{j}^{T})\geq w_{t}(p_{j}^{t})$
(the latter inequality holds because if $t=T$, this is true by definition, and
if $t>T$, then $f(t,T)=\beta_{T}(t-T)>\beta_{t+1}$.) It is not possible for
$c_{j}^{T}$ to be $\beta_{t+2}$-attached to $p_{j^{\prime}}^{t}$ w.r.t.
$w_{t+1}$ for $j^{\prime}\in[t]\setminus j$ , since this would mean
$c_{j}^{T}$ is $\beta_{t+2}$-attached to $p_{j^{\prime}}^{t}$ w.r.t. $w_{t}$
as well. But if this were true, then we get a contradiction by Proposition 5,
because $p_{j}^{t}$ and $p_{j^{\prime}}^{t}$ are $\beta_{t}$-well-separated
w.r.t. $w_{t}$ by the inductive assumption. Also, it is not possible for
$c_{j}^{T}$ to be $\beta_{t+2}$-attached to $p_{j^{*}}^{t+1}=c_{j^{*}}^{T}$
w.r.t. $w_{t+1}$, thus also w.r.t. $w_{i-1}$, by Fact 2. So either $c_{j}^{T}$
is $\beta_{t+2}$-well-separated from
$\\{p_{1}^{t},\dots,p_{t}^{t},c_{j^{*}}^{T}\\}=\\{p_{1}^{t+1},\dots,p_{t+1}^{t+1}\\}$
w.r.t. $w_{t+1}=w_{i}$; or, $c_{j}^{T}$ is $\beta_{t+2}$-attached to
$p_{j}^{t}=p_{j}^{t+1}$ w.r.t. $w_{t+1}$. So statement (a) or statement (b)
must hold for $t+1$.

In the remaining cases of the Add Operation, it is not possible that statement
(a) holds in the inductive assumption for $t$, for then Case 1 of the Add
Operation would have been executed. Thus we can omit statement (a) from the
casework.

######  Case 2.

Case 2 of the Add Operation is executed.

If statement (c) holds in the inductive assumption for $t$. The reasoning is
the same as in Case 1 (except there is no distinguished $j^{*}$).

Else statement (b) holds in the inductive assumption for $t$. Since statement
(c) does not hold, we have $w_{t}(c_{j}^{T})\geq w_{t}(p_{j}^{t})$ (the
reasoning is the same as in Case 1). But by the assumptions of Case 2 of the
Add Operation, this means that $c_{j}^{T}$ is $\beta_{t+2}$-well-separated
from $x_{\alpha}$ w.r.t. $w_{i}$. So either $c_{j}^{T}$ is $\beta_{t+2}$-well-
separated from
$\\{p_{1}^{t},\dots,p_{t}^{t},x_{\alpha}\\}=\\{p_{1}^{t+1},\dots,p_{t+1}^{t+1}\\}$
w.r.t. $w_{i}$, or $c_{j}^{T}$ is $\beta_{t+2}$-attached to
$p_{j}^{t}=p_{j}^{t+1}$ w.r.t. $w_{i}=w_{t+1}$, by the same reasoning as in
Case 1 (except there is no distinguished $j^{*}$). So statement (a) or
statement (b) must hold for $t+1$.

######  Case 3.

Case 3 of the Add Operation is executed.

Let $j^{*}$ be as in $j$ chosen in Case 3 of the Add Operation. We need to
show that for every $j\in[T]$, at least one of statements (a)—(c) holds for
$t+1$.
If $j=j^{*}$, then $p_{j}^{t+1}=x_{\alpha}$, and by definition of $j^{*}$,
$c_{j}^{T}$ is $\beta_{t+2}$-attached to $p_{j}^{t+1}$ w.r.t. $w_{i}=w_{t+1}$,
so statement (b) is satisfied for $t+1$.
Now we consider $j\neq j^{*}$. We case on which of statements (a)—(c) holds
for $j\in[T]$ in the inductive assumption for $t$.

If statement (c) holds in the inductive assumption for $t$. The reasoning is
the same as in Case 1.

Else statement (b) holds in the inductive assumption for $t$. Note that since
$w_{t}(c_{j}^{t})\geq w_{t}(p_{j}^{t})$ and $j\neq j^{*}$ (for the same
reasoning as in Case 1), $c_{j}^{T}$ is $\beta_{t+2}$-well-separated from
$p_{j^{*}}^{t+1}=x_{\alpha}$ w.r.t. $w_{i}$ (by the assumptions of Case 3 of
the Add Operation and the uniqueness of $j^{*}$). Now the reasoning is the
same as in Case 1.

######  Case 4.

Case 4 of the Add Operation is executed.

Let $f$ or $g$ be as in Case 4 of the Add Operation. We need to show that for
every $j\in[T]$, at least one of the statements (a)—(c) holds for $t+2$. (Note
phase $t+1$ is skipped.) If $j=f$ or $g$, then $p_{j}^{t+2}=c_{j}^{T}$, so
certainly $c_{j}^{T}$ is $\beta_{t+3}$-attached to $p_{j}^{t+2}$ w.r.t.
$w_{t+2}$, so statement (b) is satisfied for $t+2$. Now we consider $j\neq
f,g$. We case on which of statements (a)—(c) held for $j\in[T]$ in the
inductive assumption for $t$.

If statement (c) holds in the inductive assumption for $t$. The reasoning is
nearly the same as in Case 1, except now there are two distinguished $f,g$
(instead of just $j^{*}$), and we use that $f(t+2,T)>f(t,T)$ (instead of that
$f(t+1,T)>f(t,T)$).

Else statement (b) holds in the inductive assumption for $t$. Note that since
$j\neq f,g$, $c_{j}^{T}$ is $\beta_{t+3}$-well-separated from
$p_{f}^{t+2}=c_{f}^{T}$ w.r.t. $w_{i}$ and from $p_{g}^{t+2}=c_{g}^{T}$ w.r.t.
$w_{i}$, by Fact 2. By the same reasoning as in Case 1, either $c_{j}^{T}$ is
$\beta_{t+3}$-attached to $p_{j}^{t+2}=p_{j}^{t}$ w.r.t. $w_{i}$, or
$c_{j}^{T}$ is $\beta_{t+3}$-well-separated from
$\\{p_{1}^{t},\dots,p_{t}^{t},c_{f}^{T},c_{g}^{T}\\}=\\{p_{1}^{t+2},\dots,p_{t+2}^{t+2}\\}$
w.r.t. $w_{i}$. So statement (a) or statement (b) must hold for $t+2$.

In all cases of the Exchange Operation, it is not possible that statement (a)
holds in the inductive assumption for $t$, for then an Add Operation
(specifically Case 1) would have been executed instead, as the Add Operation
takes precedence over the Exchange Operation. Thus we can omit statement (a)
from the casework. Let $j^{*}$ be the specific $j$ in the description of the
Exchange Operation in the algorithm description.

######  Case 5.

Case 1 of the Exchange Operation is executed.

We need to show that for every $j\in[T]$, at least one of statements (a)—(c)
holds for $t+1$.
If $j=j^{*}$, there is nothing to prove because in Case 1 of the Exchange
Operation, $j^{*}>T$, meaning $c_{j^{*}}^{T}$ is not defined.
Now we consider $j\neq j^{*}$. We case on which of statements (a)—(c) holds
for $j\in[T]$ in the inductive assumption for $t$.

If statement (c) holds in the inductive assumption for $t$. The reasoning is
the same as in Case 1.

Else statement (b) holds in the inductive assumption for $t$. We first claim
$c_{j}^{T}$ is $\beta_{t+1}$-attached to $p_{j}^{t}=p_{j}^{t+1}$ w.r.t.
$w_{t+1}$ (note (b) states this w.r.t. $w_{t}$ only). For, given that
$c_{j}^{T}$ is $\beta_{t+1}$-attached to $p_{j}^{t}$ w.r.t. $w_{t}$ and
$w_{t}(c_{j}^{T})\geq w_{t}(p_{j}^{t})$, it must be the case that $c_{j}^{T}$
is $\beta_{t+1}$-well-separated from $p_{j^{\prime}}^{t}$ w.r.t. $w_{t}$, for
any $j^{\prime}\neq j$ (by Proposition 5 and the fact that $p_{j}^{t}$ and
$p_{j^{\prime}}^{t}$ are $\beta_{t}$-well-separated w.r.t. $w_{t}$). But this
means that $c_{j}^{T}$ is $\beta_{t+1}$-well-separated from
$p_{j^{\prime}}^{t}$ w.r.t. $w_{t+1}$ as well. Thus, if $c_{j}^{T}$ were not
$\beta_{t+1}$-attached to $p_{j}^{t}$ w.r.t. $w_{t+1}$, then it would be
$\beta_{t+1}$-well-separated from $\\{p_{1}^{t},\dots,p_{t}^{t}\\}$ w.r.t.
$w_{t+1}=w_{i}$, hence an Add Operation would have been executed instead as
the Add Operation takes precedence over the Exchange Operation. So we conclude
that $c_{j}^{T}$ is $\beta_{t+1}$-attached to $p_{j}^{t}=p_{j}^{t+1}$ w.r.t.
$w_{t+1}$.
If $w_{t+1}(c_{j}^{T})<w_{t+1}(p_{j}^{t})$, then since $t+1>T$, statement (c)
holds for $t+1$. Otherwise, $w_{t+1}(c_{j}^{T})\geq w_{t+1}(p_{j}^{t})$. Also,
$w_{t+1}(x_{\alpha})\geq w_{t+1}(p_{j^{*}}^{t})$ and $x_{\alpha}$ is
$\beta_{t+1}$-attached to $p_{j^{*}}^{t}$ w.r.t. $w_{t+1}=w_{i}$, by
definition of the Exchange Operation. So noting that $p_{j}^{t}$ and
$p_{j^{*}}^{t}$ are $\beta_{t}$-well-separated w.r.t. $w_{t+1}$ and applying
Proposition 5 twice gives that $c_{j}^{T}$ is $\beta_{t+2}$-well-separated
from $x_{\alpha}$ w.r.t. $w_{t+1}$ (and likewise for $x_{\gamma}$). We also
know that $c_{j}^{T}$ is $\beta_{t+2}$-well-separated from
$p_{j^{\prime}}^{t}$ w.r.t. $w_{t+1}$, $j^{\prime}\neq j$, by the previous
paragraph. So either $c_{j}^{T}$ is $\beta_{t+2}$-attached to
$p_{j}^{t}=p_{j}^{t+1}$ w.r.t. $w_{t+1}$, or $c_{j}^{T}$ is
$\beta_{t+2}$-well-separated from
$\\{p_{1}^{t},\cdots,p_{t}^{t},x_{\alpha},x_{\gamma}\\}\setminus\\{p_{j^{*}}^{t}\\}=\\{p_{1}^{t+1},\dots,p_{t+1}^{t+1}\\}$.
Thus statement (a) or (b) holds for $t+1$.

######  Case 6.

Case 2 of the Exchange Operation is executed.

We need to show that for every $j\in[T]$, at least one of statements (a)—(c)
holds for $t+1$.
First consider $j=j^{*}$. Since as noted above statement (a) cannot hold for
the inductive assumption for $t$, statement (b) or statement (c) must hold for
the inductive assumption for $t$. Also, since $w_{t+1}=w_{i}$, it must be the
case that $w_{t+1}(c_{j}^{T})<w_{t+1}(p_{j}^{t})$ by the assumptions of Case 2
of the Exchange Operation. Thus $w_{t}(c_{j}^{T})\leq w_{t}(p_{j}^{t})$.

If $t=T$, then it must be the case that $w_{t}(c_{j}^{T})=w_{t}(p_{j}^{t})$
hence $c_{j}^{T}=p_{j}^{t}$ by the tiebreaking rule in the definition
($\ddagger$ ‣ 4.1) of estimated center. If $t>T$, then since
$w_{t}=w_{t+1}=w_{p}$, statement (c) holds for $t$. So in both cases,
$w_{i}(c_{j}^{T})\cdot d(c_{j}^{T},p_{j}^{t})\leq\beta_{T}(t-T)$. Moreover, by
the definition of the Exchange Operation, $w_{i}(p_{j}^{t})\cdot
d(p_{j}^{t},p_{j}^{t+1})=w_{i}(p_{j}^{t})\cdot
d(p_{j}^{t},x_{\alpha})\leq\beta_{t+1}\cdot\textsf{OPT}$. So by Proposition 5,
$w_{i}(c_{j}^{T})\cdot
d(c_{j}^{T},x_{\alpha})\leq(\beta_{t+1}+f(t,T))\textsf{OPT}\leq
f(t+1,T)\textsf{OPT}$. Hence statement (c) holds for $t+1$.

For $j\neq j^{*}$, the reasoning is the same as in Case 5.

######  Case 7.

Case 3 of the Exchange Operation is executed.

We need to show that for every $j\in[T]$, at least one of statements (a)—(c)
holds for $t+1$.
First consider $j=j^{*}$. By the assumptions of of Case 3 of the Exchange
Operation, statement (b) holds for $t+1$.

For $j\neq j^{*}$, the reasoning is the same as in Case 5.

######  Case 8.

Case 4 of the Exchange Operation is executed.

The reasoning is the same as in Case 7, only now the roles of
$x_{\alpha},x_{\gamma}$ are reversed.

######  Case 9.

Case 5 of the Exchange Operation is executed.

We need to show that for every $j\in[T]$, at least one of statements (1)–(3)
holds for $t+2$. (Note step $t+1$ is skipped.)
First consider $j=j^{*}$. $c_{j^{*}}^{T}$ is $\beta_{t+3}$-attached to
$p_{j^{*}}^{t+2}=c_{j^{*}}^{T}$ w.r.t. $w_{t+2}$, so statement (b) holds for
for $t+2$.
For $j\neq j^{*}$, $c_{j}^{T}$ is $\beta_{t+3}$-well-separated from
$c_{j^{*}}^{T}$ w.r.t. $w_{i}$ (Fact 2). The reasoning is now the same as in
Case 5 once we note that $\beta_{t+2}>\beta_{t+3}$. ∎ Having proven
Proposition 4, the proof of Lemma 1 is now complete. ∎

##  Appendix D Omitted Proofs from Section 6.1

###### Proof of Lemma 4.

As in Lemma 3, let $C_{j}=C_{j}^{T}\setminus C_{j}^{T^{-}}$ and let $S_{ji}$
be the set of elements in $C_{j}$ assigned to $y_{i}$ in the clustering of
$X(T)\setminus X(T^{-})$ induced by $P_{T}$. Let
$S_{far,j}=\bigcup_{i:p(y_{i})\neq p_{j}^{T}}S_{ji}$,
$S_{near,j}=\bigcup_{i:p(y_{i})=p_{j}^{T}}S_{ji}$, and $S_{j}$ be the elements
in $C_{j}$ that are assigned to $p_{j}^{T}$ in the clustering of
$X(T)\setminus X(T^{-})$ induced by $P_{T}$.

The proof is by induction. We have that

$|C_{j}^{T}|=|C_{j}^{T^{-}}|+|C_{j}|=|C_{j}^{T^{-}}|+|S_{far,j}|+|S_{near,j}|+|S_{j}|$
(10)

(Note we use that there are no points in $C_{j}$ that are assigned to
$p_{j^{\prime}}^{T}$, $j^{\prime}\neq j$, in the offline clustering induced by
$P_{T}$, due to the greedy labelling rule. This is true as long as in the
offline clustering induced by $P_{T}$ we break ties consistent with how the
online algorithm breaks ties.)

First, we bound the last three terms. Let $w^{t}$ denote the natural weights
at the end of phase $t$.

$|S_{far,j}|\leq k\cdot w^{T}(p_{j}^{T})\leq k\cdot w^{T}(c_{j}^{T})$ (11)

where the first inequality follows from Lemma 3 and the second inequality
follows from the definition ($\ddagger$ ‣ 4.1) of estimated center. Next,

$|S_{near,j}|=\sum_{i:p(y_{i})=p_{j}^{T}}|S_{ji}|\leq\sum_{i:p(y_{i})=p_{j}^{T}}w^{T}(y_{i})\leq
k\cdot w^{T}(c_{j}^{T})$ (12)

where the second inequality follows from the definition of $w^{T}$. The third
inequality follows from the definitions of attachment digraph and estimated
center: If $y_{i}\in\delta^{-}(p_{j}^{T})$, then $w^{T}(y_{i})\leq
w^{T}(p_{j}^{T})$ by construction of the attachment digraph $D(T)$. Otherwise,
$y_{i}\in\delta^{+}(p_{j}^{T})$, so by ($\ddagger$ ‣ 4.1),
$w^{T}(c_{j}^{T})\geq w^{T}(y_{i})$. Finally,

$|S_{j}|\leq w^{T}(p_{j}^{T})\leq w^{T}(c_{j}^{T})$ (13)

where the first inequality is by the definition of $w^{T}$ and the second
inequality from ($\ddagger$ ‣ 4.1).

For simplicity, let $h(t,k)=(2k+1)t$. Now we need to bound $|C_{j}^{T-}|$ in
terms of $w^{T}(c_{j}^{T})$. If $j\not\in[T^{-}]$, then $|C_{j}^{T^{-}}|=0$.
So assume $j\in[T^{-}]$. Inductively, we have that

$|C_{j}^{T^{-}}|\leq h(T^{-},k)\cdot w^{T^{-}}(c_{j}^{T^{-}}).$

We will prove that

$|C_{j}^{T^{-}}|\leq h(T^{-},k)\cdot w^{T}(c_{j}^{T}).$ (14)

There are two cases to consider.

######  Case 1.

(a) holds in Lemma 2.

$|C_{j}^{T^{-}}|\leq h(T^{-},k)\cdot w^{T^{-}}(c_{j}^{T^{-}})\leq
h(T^{-},k)\cdot w^{T}(p_{j}^{T})\leq h(T^{-},k)\cdot w^{T}(c_{j}^{T}).$

######  Case 2.

(b) holds in Lemma 2.

This means that $c_{j}^{T^{-}}$ is $\beta_{T+1}$-attached to $p_{j}^{T}$
w.r.t. $w^{T}$. If $w^{T}(c_{j}^{T^{-}})\leq w^{T}(p_{j}^{T})$, then
$w^{T}(c_{j}^{T^{-}})\leq w^{T}(c_{j}^{T})$. Otherwise,
$w^{T}(c_{j}^{T^{-}})>w^{T}(p_{j}^{T})$, so
$c_{j}^{T^{-}}\in\delta^{+}(p_{j}^{T})$. By ($\ddagger$ ‣ 4.1),
$w^{T}(c_{j}^{T^{-}})\leq w^{T}(c_{j}^{T})$. In both cases we have
$w^{T}(c_{j}^{T^{-}})\leq w^{T}(c_{j}^{T})$, so building from the inductive
assumption,

$|C_{j}^{T^{-}}|\leq h(T^{-},k)\cdot w^{T^{-}}(c_{j}^{T^{-}})\leq
h(T^{-},k)\cdot w^{T}(c_{j}^{T^{-}})\leq h(T^{-},k)\cdot w^{T}(c_{j}^{T})$

which concludes the case. Putting equations (10), (11), (12), (13), (14)
together gives

$|C_{j}^{T}|\leq\left(h(T^{-},k)+2k+1\right)\cdot w^{T}(c_{j}^{T})\leq
h(T,k)\cdot w^{T}(c_{j}^{T})=(2k+1)\cdot T\cdot w^{T}(c_{j}^{T})$

as desired.

∎

##  Appendix E Decreasing the well-separation parameter is necessary.

Due to the relatively static nature of our algorithm (we only reset the pivots
at most $k$ times), it is perhaps not surprising that we will have to
initialize the well-separation parameter $\beta_{1}$ to be large, and then
decrease it as we create more pivots. As a result, our algorithm will
accumulate $\Omega(poly(k)2^{k})$ cost. Next, we show decreasing $\beta$ is
necessary to avoid accumulating infinite cost.

In fact, we require $\beta_{t+1}\leq\beta_{t}/2$. See Figure 6. Let the phase
be $t=2$ and $p_{1}^{2}$ and $p_{2}^{2}$ denote the pivots in phase 2,
associated with labels 1 and 2, respectively. Let $\beta=\beta_{2}$ and
$\varepsilon>0$.

By the time phase 2 starts, the only points that have arrived are one point
each at $p_{1}^{2}$ and $p_{2}^{2}$. Note that since $p_{1}^{2}$ and
$p_{2}^{2}$ are distance $\beta$ apart, they satisfy the invariant that the
pivots at the start of phase 2 should be $\beta=\beta_{2}$-well-separated
w.r.t. the natural weights at the start of phase 2. Suppose we do not require
$\beta_{3}\leq\beta_{2}/2$. If this is the case, we may have infinitely many
points arrive at $x$ and $y$, without ever being able to make three pivots.
Moreover, since we assign points to pivots greedily, the infinitely many
points at $x$ and $y$ would be assigned the same label, yielding a cluster
with unbounded cost. To see that three pivots could never be made, note that
$p_{1}^{2}$ prevents us from adding $x$ as a pivot, since $p_{1}^{2}$ and $x$
are $(\beta/2+\varepsilon)$-attached at any point in time (even though there
are infinitely many points at $x$). Likewise, $p_{2}^{2}$ prevents us from
adding $y$ as a pivot. So as long as at least one of $p_{1}^{2}$ or
$p_{2}^{2}$ must remain a pivot (which must be the case if we are to increase
the number of pivots to three, as there are only four locations in this
example), it is impossible to have $\beta_{3}>\beta_{2}/2$ without
accumulating infinite cost.

Figure 6: The case discussed in Appendix E showing that the well-separation
parameter $\beta_{t}$ for phase $t$ must decrease by a factor of at least 2
with $t$.

##  Appendix F Avoiding label conflicts.

Each pivot must be associated with a distinct label. The situation we have to
handle delicately is when we are resetting pivots and two center estimates for
two different online clusters are each close to the candidate new pivot;
however, the candidate new pivot can only be associated with one label. See
Figure 7. There are three present pivots, $p_{1}^{2},p_{2}^{3},p_{3}^{3}$, and
the candidate new pivot is $x$, which is $\beta_{4}$-well-separated from the
pivots $p_{1}^{3}$ and $p_{2}^{3}$ for labels 1 (blue) and 2 (green),
respectively. However, $x$ is also “close” ($\beta/5$-attached, specifically)
to the estimated centers $c_{1}^{3}$ and $c_{2}^{3}$ for clusters 1 and 2,
respectively, so if we were to add $x$ as a pivot, it would be unclear as to
whether we should give it the label 1 or 2. Instead, we will not actually add
the candidate new pivot; we can show that the two center estimates $c_{1}^{3}$
and $c_{2}^{3}$ can be added as the pivots for the labels 1 and 2,
respectively, while ensuring that all five pivots are $\beta/5$-well-
separated. The old locations for pivots $p_{1}^{3}$ and $p_{2}^{3}$ are now
the locations for the pivots of the new labels 4 (red) and 5 (purple). This
situation is encoded in Case 4 of the Add Operation in Section 4.2.

Figure 7: The situation described in Appendix F in which we must add two
pivots in one shot in order to avoid label conflicts. Dashed lines indicate
well-separation and solid lines indicate attachment, labelled with the
appropriate parameters. Arrows go from smaller to larger natural weights.