Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
Authors: Sayan Bhattacharya
Martin Costa
Ermiya Farokhnejad
Silvio Lattanzi
Nikos Parotsidis
Venue: ICML 2025 poster (2025)
Keywords: clustering algorithm
$k$-center
dynamic algorithms
approximation algorithms
Primary area: general_machine_learning->clustering
TL;DR: We give a simple algorithm for dynamic $k$-center that maintains a $O(1)$-approximate solution with $O(1)$ amortized recourse and $\tilde O(k)$ amortized update time, obtaining near-optimal approximation, recourse and update time simultaneously.

Abstract: In this paper, we consider the *metric $k$-center* problem in the fully dynamic setting, where we are given a metric space $(V,d)$ evolving via a sequence of point insertions and deletions and our task is to maintain a subset $S \subseteq V$ of at most $k$ points that minimizes the objective $\max_{x \in V} \min_{y \in S}d(x, y)$. We want to design our algorithm so that we minimize its *approximation ratio*, *recourse* (the number of changes it makes to the solution $S$) and *update time* (the time it takes to handle an update). We give a simple algorithm for dynamic $k$-center that maintains a $O(1)$-approximate solution with $O(1)$ amortized recourse and $\tilde O(k)$ amortized update time, *obtaining near-optimal approximation, recourse and update time simultaneously*. We obtain our result by combining a variant of the dynamic $k$-center algorithm of Bateni et al. [SODA'23] with the dynamic sparsifier of Bhattacharya et al. [NeurIPS'23].

Almost Optimal Fully Dynamic k-Center Clustering with Recourse
Sayan Bhattacharya' Martín Costa'
Ermiya Farokhnejad
Silvio Lattanzi? Nikos Parotsidis'
Abstract
els (Charikar al., 1999; Jain & Vazirani, 2001; Ahmadian et al., 2019; Byrka et al., 2017: Charikar et al., 2003; Ailon et al., 2009; Shindler et al., 2011; Borassi et al., 2020). In this paper, we focus on the k-center problem, where the ob- jective function is defined as cl(S, V) == maxzev d(xr, S), where d(x, S) == minges d(x,, y). In other words, we want to minimize the maximum distance from any point in V to its nearest point in S.
In this paper, we consider the metric k-center problem in the fully dynamic setting, where we are given a metric space (V,d) evolving via a sequence of point insertions and deletions and our task is to maintain a subset C V of at most k points that minimizes the objective maX minges d(a, y). We want to design our algorithm so that minimize its approximation ratio, recourse (the number of changes it makes to the solution S) and update time (the time it takes to handle an update). We give a simple al- gorithm for dynamic k-center that maintains a -1ppapppox solution with (1)) amortized recourse and Ō(k) amortized update time, obtain- ing near-optimal approximation, recourse and up- date time simultaneouslyy. We obtain our result by combining a variant of the dynamic k-center algo- rithm of Bateni et al. (SODA'23) with the dynamic sparsifier of Bhattacharya et al. [NeurIPS' 23].
The dynamic setting:
In recent years, massive and rapidly changing datasets have become increasingly common. If we want to maintain good solution to a problem defined on such a dataset, it is often not feasible to apply standard com- putational paradigms and recompute solutions from scratch using static algorithms every time the dataset is updated. As a result, to cope with real world-scenarios, significant effort has gone into developing dynamic algorithms that are capable of efficiently maintaining solutions as the underly- ing dataset evolves over time (Bhattacharya et al., 2023b; Behnezhad et al., 2019).
In the case of dynamic clustering, the most practical and studied setting is one where the metric space (V, d)) evolves over time via a sequence of updates that consist of point insertions and deletions. Dynamic clustering has received a lot of attention from both the theory and machine learning communities over the past decade (Lattanzi & Vassilvitskii, 2017; Chan et al., 2018; Cohen-Addad et al., 2019; Hen- zinger & Kale, 2020; Bhattacharya et al., 2022; Goranci et al., 2021; Bhattacharya et al., 2024a). This long and in- fluential line of work ultimately aims to design dynamic clustering algorithms with optimal guarantees, mainly fo- cusing the following three metrics: (I) the approximation ratio of the solution S maintained by the algorithm, (II) the update time of the algorithm, which is the time it takes for the algorithm to update its solution after a point is inserted or deleted, and (III) the recourse of the solution, which is how many points are added or removed from S after an update is performed!' These three peerres-approximmaaio ratio, update time, and recourse-capture the essential qualities of a good practical dynamic clustering algorithm: solution quality, efficiency, and stability.
1. Introduction
Clustering data is a fundamental task in unsupervised learn- ing. In this task, we need to partition the elements of a dataset into different groups (called clusters) so that cle- ments in the same group are similar to each other, and elements in different groups are not.
One of the most studied formulations of clustering is metric k-clustering, where the data is represented by points in some underlying metric space (V, d), and we want to find a subset S C V of at most & centers that minimizes some objective function. Due to its simplicity and extensive real-world applications, metric k-clustering has been studied exten- sively for many years and across many computational mod-
'Department of Computer Science, University of War- wick 'Google Research. Correspondence to: Sayan Bhat- tacharya <s.bhattacharya@G wawwick.ac..k>. Martín Costa <martin.costa @ warwick.ac ac.ukk uk> Ermiya Farokhnejad <er- tiiya.farokhneaaeee warwick.ac.uk .uk>, Silvio Lattanzi <sil-
viol @ google.com. Nikos Parotsidis <nikosp@ ceoss@@googl..oom google.com>.
"In other words. if we let S and S' denote the solution main- tained by the algorithm before and after update. then we define the recourse of the update to |S @ S'), where T denotes sym- metric difference.
Proceedings of the 4 International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Almost Optimal Fully Dynamic &- d-Center Clustering with Recourse
The state-of-the-art for dynamic k-center: The classic algorithm of (Gonzalez, 1985) returns 2-approxmiation to the k-center problem in ((n)) time in the static setting, where n is the size of the metric space V. It is known to be NP-hard to obtain a (2 <) >>approxximation for >> 0 and that any (non-trivial) approximation algorithm for k-center has running time ()(kk (Bateni et al., 2023). Thus, the best we can hope for in the dynamic setting to maintain
et al., 2023). Even though the high-level framework used by (Bateni et al., 2023) is quite simple, they require signif- icant amount of technical work to obtain good update time; we bypass this by using the dynamic sparsifier of (Bhat- tacharya et al., 2023a), giving a very simple variant of their algorithm that has good recourse and can be implemented efficiently using the dynamic MIS algorithm of (Behnezhad et al., 2019) as a black box.*
2-approximation in O(k) update time. Bateni et al (Bateni et al., 2023) showed how to maintain (2-re--aproximmatin to k-center in ((k/e) update time, obtaining near-optimal approximation and update time. However, their algorithm does not have any non non-trivial bound on the recourse (the solution might change completely between updates, lead- ing to a recourse of (2())). In subsequent work, Lacki et al. (Lacki et al., 2024) showed how to maintain a (1)) approximation with O11) recourse, achieving worst-case recourse of 4. The algorithm of (Lacki et al., 2024) does however have a large (poly(n)) update time, with the authors stating that it would be interesting to obtain an up- date time of (ppoly())). This was very recently improved upon by (Forster& Skarlatos, 2025), who showed how to obtain an optimal worst-case recourse of 2.3 Very recently, Bhattacharya et al. (Bhattacharya et al., 2024a) showed how to maintain a Olog n log apprroxxxmttoo with Ō(k) up- date time and (1) recourse, obtaining near-optimal update time and recourse simultaneously, but with polylogarithmic approximation ratio.
Related work: It was first shown how to maintain (2 c)- approximation to k-center with Ö(L²) update time by (Chan et al., 2018); the algorithm of (Chan et al., 2022) improved the space efficiency of this algorithm, but at the cost of obtaining a (4 + e)-approximation Dynamic k-clustering has also been explored in various other settings; there are lines of work that consider the specific settings of Euclidean spaces (Bateni et al., 2023; Bhattacharya et al., 2024b), other k-clustering objectives such as k-median, k-means and facility location (Cohen-Addad et al., 2019; Henzinger & Kale, 2020; Bhattacharya et al., 2023a; 2024a; 2022; 2025), additional constraints such as outliers (Biabani et al., 2023) and the incremental (insertion only) setting, where the objective is to minimize recourse while ignoring update time (Lattanzi & Vassilvitskii, 2017: Fichtenberger et al., 2021). A separate line of work considers metric spaces of bounded doubling dimension, where it is known how to maintain a (2 (2+e)-aan -approximmatoon to k-center in Ô(1) update time (Goranci et al., 2021; Gan & Golin, 2024: Pellizzoni et al., 2025). (Cruciani et al., 2024) also considered the problem of dynamic k-center w.r.t. the shortest path metric graph undergoing edge insertions and deletions.
Ultimately, we want to obtain near-optimal approximation, update time and recourse simultaneously. Each of the algo- rithms described above falls short in one of these metrics, having either poor approximation, update time or recourse. This leads us to the following natural question:
1.1. Technical Overview
We obtain our result by combining a simple variant of the algorithm of (Bateni al., 2023) with the dynamic sparsi- fication algorithm of (Bhattacharya et al., 2023a). In this technical overview, we give an informal description of a variant of the algorithm of (Bateni et al., 2023), and then explain how it can be modified to obtain our result.
Q: Can we design a dynamic k-center algorithm with O(1) Japroximmtionn, (kk) update time and O(1) recourse?
We give an algorithm for dynamic k- center that answers this question in the affirmative, obtaining the following result.
Our contribution:
The algorithm of (Bateni et al., 2023): The dynamic al- gorithm of (Bateni et al., 2023) works by leveraging the well-known reduction from k-center to maximal indepen- dent set (MIS) using threshold graphs (see Definition 1.6) (Hochbaum & Shmoys, 1986).
Theorem 1.1 (informal). There is an algorithm for dy- namic k-center that maintains 20-approximation with Olk (n))()) log A) update time and 0(1) recourse.
The algorithm maintains a collection of Ô(1) many thresh- old graphs {Gx, of (V, d) and MISS {I,}; of these thresh- old graphs for values X; that increase in powers of (1 + +),
We emphasise that our algorithm is significantly simpler than the state-of-the-arr dynamic k-center al algorithms de- scribed above. Our starting point is the algorithm of (Bateni
"The Ö(-) notation hides polylogarithmic factors in n and the aspect ratio of the metric space A (see Section 1.2).
*For ease of exposition, we avoid discussing certain details of the algorithms in the introduction, such as oblivious vs. adaptive adversaries, amortized vs. worst-case guarantees, and on. Ta- ble in Appendix A contains more comprehensive summary of the state-of-ther trt algorithms for fully dynamic k-center in general metric spaces.
'We note that (Lacki et al., 2024; Forster & Skarlatos, 2025) define the recourse of an update as the number of centers that are swapped assuming that the size of the solution is always k. Thus, the bounds in their papers are smaller by a factor of 2.
2

---

Almost Optimal Fully Dynamic &- s-Center Clustcring with Recourse
i.e. A, = (1 e)) A1-1- The MISs {I,); satisfy the fol- lowing property: Let i be the smallest index such that [Z, S k, then I.- is a (2 + -ippoopipoonnaatonn to the k-center problem problem on (V, d). At any point in time, the output of this algorithm is the MIS I
V and a distance function d : V V R such that d(x, x) 0, d(x,, v) d(y, x) and d(x, y) I d(x, =) + d(z, y) for all x, y E V. We refer to the pair (V, d) as metric space.
The aspect ratio of (V, d) is defined as the ratio between the maximum and minimum non-zero distance of any two points in the space. For each S - V and x E V, we denote the distance from x to S by d(x, S) == minges d(z, y). The ball around x E V of radius r is defined as B r) {v E V d(xz, v) r]
Implementation: Using the dynamic MIS algorithm of Behnezhad et al. (2019) as a black box, which can main- tain an MIS under vertex insertions and deletions in O(n) update time, we can implement this algorithm with ((n) update time. We note that this algorithm is simple variant of the actual algorithm presented in (Bateni et al., 2023), which is much more technical. Since they want an update time of Ökk), it is not sufficient to use the algorithm of (Behnezhad et al., 2019) as a black box and instead need to use the internal data structures and analysis intricately. We later improve the update time to (k)) using a completely different approach.
Metrie k-center: In the metric k-center problem, we are given a metric space (V,d) and the objective is to find S S V of size at most k that minimizes cI(S, V) :- m d(x,S)) We denote the cost of the optimum solu- tion to the k-center problem by
OPT = min clss.)).
Obtaining good recourse: It's known how to maintain a stable MIS of dynamic graph, so that vertex updates in the graph lead to few changes in the MIS (Behnezhad et al., 2019). However, the main challenge that we encounter while trying to obtain good recourse is that the MISs {Ia}e do not necessarily have any relation to each other. Thus, whenever the index i' changes, the recourse could be as bad as (k)... By modifying the algorithm, we can ensure that the MISS {Ti}; are nested, and thus switching between them does not lead to high recourse. This leads to the following theorem.
SCV.ISis
We sometimes abbreviate cl(S, V) by cI(S) and OPT&(V) by OPT; when the set V is clear from the context.
Definition 1.6 (1-Threshold Graph). Given a metric space (V, d) and any À 2 O, we define the X-threshold graph of (V. d) to be the graph Gx == (V, Ex) where E. == (I, E (X) d(x,y) S A}.
Definition 1.7 (Bicriteria Approximation), Given a p-metric space (V,d), we say that a subset of points U C V is (a, -)-ppproxinaaionn the (k, p)clusteeiingg problem if
Theorem 1.2. There an algorithm for dynamic k- center against oblivious adversaries that maintains an 8-approximation with Onn log' (n) log A) expected worst- case update time and 4 expected worst-case recourse.
(l) S a (V) and |U| .kk
Definition 1.8 ((a, -)--Srrssiiii)).. a 2 1 and clus- tering problem. An (a., {)-sparsifier is a dynamic algorithm that, given a p-metric space (V, d) undergoing point inser- tions and deletions, maintains U C V which is an (a, 8)- approximation for the clustering problem at any point in time. The recourse of the sparsifier is defined as the number of insertions and deletions of the points in the maintained solution U.
To improve the update time from Ö(n) Ö(k), we use the dynamic sparsifier of (Bhattacharya et al., 2023a). This allows us to assume that the underlying metric space has size Ö(k), thus leading to an update time of Ö(k). This leads to the following theorem.
Theorem 1.3. There is an algorithm for dynamic k- center against oblivious adversaries that maintains a 20- approximation with Ok log" (og(() update time and (1) expected amortized r
For any natural number N, we denote the set by [N]. Consider a sequence of updates 0 Ør. For each point set U that is maintained explicitly by our algo- rithm, we use (1()) (for any t E [T') to indicate the status of this set after handling update o, For instance, if S is the so- lution maintained by our algorithm, stt) is the output after handling update o,, We also define (U) == (t-1)) @ (tt) to indicate the symmetric difference of the maintained set U before and after handling update dt.
N}}
(n) log A) expected amortized
Remark 1.4. Appendix C, we design different sparsifier by building on top of the sparsifier of (Bhattacharya al., 2023a), allowing to obtain recourse of most 8 + e.
1.2. Preliminaries and Notations
We now provide definitions and notations that we use throughout the paper.
2. Our Dynamic Algorithm (Theorem 1.2)
In this section, we provide our dynamic k-center algorithm for Theorem 1.2, which we call Dypamic-k-Center We begin by describing a dynamic algorithm for maximal
Definition 1.5 (Metric Space). Consider a set of points
'Here, the approximation guarantee holds w.h.p.
3

---

Almost Optimal Fully Dynamic &- s-Center Clustering with Recourse
independent set (MIS) that our algorithm uses as black box.
2 there is some y E I such that d(x,y) S 21 ) and we are done. Otherwise, since y E I,-1 \I, and I4 is an MIS, there exists some E I3 such that d(y.2) 2) S X Thus, we have that d(x, I,) S d(x,,) & d(z,y) + d(y. S + 2Ap.
If y E I, then d(x; I] Σ 2x;-1
2.1. The Algorithm Dynami CMTS
(Behnezhad et al., 2019) present an algorithm, which we refer to Dynami cMIS, that, given dynamic graph G' un- dergoing updates via a sequence of node insertions and dele- tions, explicitly maintains an MIS I of G. The following lemma summarizes the key properties of Dynami CMTS.
Lemma 2.3. For each i E [T] such that [Z,] > k. we have that X
The algorithm Dynami CMIS has an expected worst-case update time of O(n log* n) and an expected worst-case recourse of 1.6
Lemma 2.1.
Proef. Let S* denote an optimal solution the k-center problem in (V,d) and let B
B(S*, X/2) DyresB(y* Ax/2) (see Section 1.2 for the definition of the ball B(x,r)) Given any point y* E S*, and any two distinct points y.v' E I, we can see that at most one of y and y' is contained in Bly", Ar/2), otherwise d(y, y²) I d(y.y") v*) + d(y"", .3') I Ad contradicting the fact that I₃ is an MIS since (y. y E Ex,- Combining this with our assumption that |Z:] > k 2 |S it follows that Z, \ B(S x/22 A D, as otherwise by pigeonhole principle at least two different elements of I; would be contained in the same (yy", 22/2) for some y" E S*, which is in contra- diction with the above explanation. Hence cl(S*) 2 Ar/2. It follows that X S 2 OPT..
2.2. Our Algorithm: Dynamic- -Center
Let (V, d) be a dynamic metric space undergoing updates via sequence of point insertions and deletions, and let dmax and dmin be upper and lower bounds on the maximum and minimum (non-zero) distance between any two points in the space at any time throughout the sequence of updates. Let A : 2i-2 duin and G; == Gx, for each 0 S i S т, where T = logg A + 2 and A is the aspect ratio (see Section 1.2) of the underlying metric space. Note that the edge-sets of these threshold graphs are nested, i.e., Ei S ..... S E, Let Io denote the set V. Our algorithm Synamic-k-Cente maintains the following for each E [r]:
Applying Lemmas 2.2 and 2.3 and noting that [Z,-- /| > k,
we get cI(I,,) - 2Ap- = 41 S 8 OPT
An MIS I, := Dynami (M [I) of (i where G[S] denotes the subgraph of G induced by the node-set S.
We now proceed to bound the expected recourse of our algorithm. Suppose that our algorithm handles a sequence of updates oi...., oT. Consider (1(), 6, (Z.), S(4) 5,(5) for each t E [T] (recall the notation from Section 1 1.2).
Recourse:
The set I-11 \ ordered lexicographically.
The following lemma shows that the expected recourse of each I2 is small.
Let it E [r] be the smallest index such that [4. S k. Then the output S of our dynamic algorithm is the union of the set I, and the first k - [Z+|| points in the set - Iz.
Lemma 2.4. For each E E [T]. i E [r]. we have that (I,)) < 1.
2.3. Analysis of Our Algorithm
Proof. Fix any t E [T]. We prove this by induction on i. We
first note that (To)l = (V)) = 1. Now, let i E [r] and assume that the lemma holds for 1. Then 18 [I.) is the expected recourse of the solution maintained by the dy- namic algorithm Dynami cMT (MMT(((,,Z2) (Z, By Lemma 2.1, each node update in G2 [ leads to expected recourse of at most 1 in the solution maintained by this algorithm. Hence, we have that & < (8,(I=-)).. Taking ex- pectation on both sides, the lemma follows.
We begin by bounding the approximation ratio of our algo- rithm and then proceed to analyze the recourse and update time.
We now show that the set Z₁- is an 8 approximation to the k-center problem on (V, d). Since S 2 Iee, the approximation guarantee of our algorithm follows. We begin with the following simple lemmas.
Approximation ratio:
Lemma 2.2. For each i [T), have that cI( 2)g-
We now use Lemma 2.4 to bound the expected recourse of the solution S.
Proof. We prove this by induction on i. We first note that, since Io = V. elo) O. Now, let i [7] and & I,, and assume that the lemma holds for i - 1. Since cI(Z,-1) <
Lemma 2.5. For each t E [T]. B[(b,(S)]| < 4.
'The upper bound of 1 on the expected recourse follows from Theorem in (Censor-Hilll Hiilel et al., 2016).
Proof. Let j denote the value of the index i' immediately after handling the update 0:-1- If = O, we have (tt1
4

---

Almost Optimal Fully Dynamic &-Center Clustering with Recourse
" which equals the whole space at this time whose size is at most k. In this case, is obvious that [8:( =
k |Z,] elements of I,-1 \I, stored in T.' explicitly, at any time. Note that
|5t) @ (((t) < 1. If j > O, the size of the whole space, after updates ( - 1 and i, is at least k.
B[ V S ([ (Z)) < 2,
Claim We have
where the last inequality follows from Lemma 2.4. This means that the update time for maintaining each of these trees is (loo n) in expectation.
1 + | S 216, (1)6(1
In total, we can maintain all of the objects in our algorithm in On log"(n) (n) log A) update time in expectation.
Proof. Consider the following ordering on the points of V.
I, Ir I, (I I.- To \ II.
3. Improving the Update Time (Theorem 1.3)
where for each i [r], elements of I Iz are written in the lexicographic order. The output of the algorithm is exactly the first k points in this order. We assumed that stt-1) consists of Z and the first k -z, elements of z \z I, As a result, after handling update ot, [5x(ي many changes in the first k points in this order. Hence, there are at most these many deletions from 5t(-1) well as these many insertions, which concludes the claim.
We now show how to use sparsification to improve the up- date time of our algorithm to Ök+). In Section 3.1, we show how to use a sparsifier (see Definition 1.8) as a black box in order to speed up a dynamic algorithm. In Section 3.2, we describe the guarantees of sparsifier for k-center and com- bine it with The rest of the Section 3 is devoted to constructing this spar- sifier for k-center, which follows from the previous work of (Bhattacharya et al., 2023a). Since their algorithm is primar- ily designed for k-median rather than k-center, we describe the sparsifier of (Bhattacharya et al., 2023a) in Section 3.3, along with a new analysis that gives an improved bound on its approximation ratio for k-center and its recourse.
we have at most [I,) +
proving Theorem 1.3.
According to the above claim, by taking expectations and n
applying Lemma 2.4, we have that ([)) s 4.
Update time: Fix any / E [7] and i E [r]. If we delete x from Zz. then we remove the corresponding node from G[Zz). By Lemma 2. the expected time to update the MIS I in this graph after the deletion of x is Ó()). If we insert new point x into I,, we insert a node x into G[I.). To find the edges between x and other nodes, we first find the distance of x to all other points in I₁ in ((I,,)) ((n) time and then compare the distance with A₁ Again, by Lemma 2. 1, the expected time to update the MIS I,+1 in this graph after inserting the node x is On log" n).
3.1. Dynamic Sparsification
The following theorem describes the properties of the dy- namic algorithm obtained by composing a sparsifier and any dynamic algorithm for k-center problem.
Theorem 3.1. Assume we have an (as, 3)--passiff for metric k-center with Tg update time and Rs recourse, and a dynamic a A a-approximation algorithm for metric k-center with Ta(n) update time and RA(n) recourse. Then we can obtain a dynamic algorithm for metric k-center with (a.g + 20 (=20aa)-apppen approximaatin ratio, O(Ts + Rs -Ta(Bk) update time and O( RA (3k)) recourse."
Hence, we can perform both insertions into and dele- tions from I3 in time Onn n) for each i E [T]. By Lemma 2.4, the expected number of updates in I, is at most
1. Thus, we can update the graph G'[z)] and Z in ex- pected On log" r1) time. Finally, since T - Ollog A), the total time taken to update all of the graphs G[Z.] and MISS I, with On log' ( (n) log A) in expectation.
Proof. Let (V, d) be a dynamic metric space. We run the sparsifier on this space which at any point in time maintains a subset U S V. This defines a dynamic metric subspace (U, d) of size at most ßk, such that each update in V leads to at most Rss updates in U and CI V) S as OPT&
In order to maintain S. for each i, we can maintain two binary search trees T,' and T." such that T'' contains the first k - elements of I \I, and T contains the rest of elements in I \ AZ, After each insertion deletion in any I4 or I,-1. we can exchange the last element of T and the first element of T." appropriately, in order to maintain the property in the definition of T and T/". For instance after a deletion in Zg the value of [Z, increments, and we should remove the first element of T," and add it to T (which would be new last element). Hence, we have the first
Now, we feed the new dynamic subspace (U,d) (whose size is at most 3k at any time) to the k-center algorithm, which maintains a subset of points S C U of size k such that cI(S, U) S a (U). We refer to this process as composing these dynamic algorithms.
Since each update in V leads to at most Rs updates in U, it follows that the update time and recourse of the composite
Thii holds for both worst-case and amortized guarantees.
5

---

Almost Optimal Fully Dynamic k-Center Clustering with Recourse
algorithm are O + Rg (3k3)) and O(Rs (3k)) respectively. To bound the approximation ratio, consider the following claim.
et al., 2023a). Before we provide the algorithm, men- tion that in (Bhattacharya al., 2023a), the main goal is to solve the k-median problem. In particular, there are some technical details for k-median that we do not need for k- center. There is no argument for recourse of the algorithm in (Bhattacharya et al., 2023a). Here, we briefly describe the algorithm and show that the amortized recourse of this algorithm is actually (1)).
Claim 3.2. Given subsets S S U C V.V cI(S, V) V) + US)
V. we have that
Proof. Let E V. y and y' be the closest points to in S and U respectively, and y" be the closest point to y' in S. Then we have that
The algorithm Spars i fier is dynamization of well- known algorithm by Mettu and Plaxton (Mettu & Plaxton, 2002).
d(x, 5) =( d(a,v)))
(l. =(c,)) d(y. d(x, + d(y', S) s V) + (S)
The algorithm of Nettu--Plaxton The main component of this algorithm is the following key subroutine:
follows that cI V) < cI(U v) U).
A1 mostt Sample a subset S C of size 2k u.a.r, compute the subset C' S U of the [U1/4 points in U that are closest to the points in S, and return (S,U\C).
Applying Claim 3.2, we get that
cl(s.V) v cI(U, V) + Cl)
I as OPT, + a.. (U)
Intuitively, this subroutine grows balls centered at sampled points simultancously until they cover a quarter of the space. This gives a partitioning of quarter of the points into (Ik) sets, which we refer to as clusters.
< (as + 2k.) (V),
where the last inequality follows since OP) S 2 (V) for any W C V (see Lemma B.
0
The algorithm begins by setting U1 :- Vi and, while |U/] 2 @(k), repeatedly sets (S., U++1) + Almost CoverstCovee(.i))) This defines a sequence of nested subsets V = =U1 2 ... 2 Ue for E = O(lg(nn/k)) and subsets S; C U. for each E |t - 1]. The output of the
3.2. Proof of Theorem 1.3
We start with the following lemma, which provides the guarantees of a sparsifier for the k-center problem. We prove this lemma in Section 3.3.
algorithm is the set U = U.....US U Ue, which has size at most Okk) - O(k lok/o//////// (k)). Note that for each i, each point x E S, the center of a cluster and points of Ue are singleton clusters. Hence, the final clustering produced by the algorithm assigns each point x U, \ Ut+1 to its nearest center in S; (breaking the ties arbitrarily).
Lemma 3.3. There exists a (4, ((og(n//k)))sspae --saariiirr for the k-center problem on a metric space (V. d). whose ap- proximation guarantee holds with high probability, and has ((Klog(n/Ka k)) amortized update time and (1) amortized recourse. 8
The algorithm Sparsi fiarsffier: At a high level, (Bhat- tacharya et al., 2023a) dynamizes the static algorithm of Mettu-Plaxton by maintaining an approximate version of their hierarchy of nested sets, which are updated lazily and periodically reconstructed by using AlmostCover in the same way as the Mettu-Plaxton algorithm." 9 More specifi- cally, Spars fier maintains the following
Theorem 1.3 now follows by combining our algorithm Dynamic- -eamiccc--enttez from Theorem 1.2 and the spar- sifier of Lemma 3.3 by using the composition described in Theorem 3.1. The approximation ratio of the result- ing algorithm is as + 2 4 + 2-5 8 = 20 w.h.p. The expected amortized recourse is ORRs (3k)) = O(1) since both Rg and RA are constant. For the up- date time, we have Ts = (k (og(k)))))) Rs 3= loogn/kk), and (3k)) = O((3) 18k)(8k) (8k) log A) = O(k log"(n) log A). Hence, the final update time of the algorithm is OTTs + Rs (Bk))) Olk (nn(()) log A).
1,
* Subsets V = U1 2 ... 2 Ue for f = (log(( (k)))
St S U, for each E [e- 1].
U == S1 U...U S 1 U Ue as the output.
3.3. The Algorithm Sparsifies (Proof of Lemma 3.3)
We now describe how these items are updated as points are inserted and deleted from V.
The algorithm in Lemma 3.3 (which we refer to Sparsifier) follows from the results of (Bhattacharya
Herr we slightly change the algorithm as follows. We will call A mostCover multiple times instead of once, and then select the hest output among these independent calls in order boost the approximation ratio (see Lines 9 13 in Algorithm 1).
'In Appendix C, show how construct a different sparsifier, leading to a recourse most + e.
6

---

Almost Optimal Fully Dynamic &- e-Center Clustcring with Recourse
Insertion: When point x is inserted into V, a is added to each set in Ui,.... Ug. In this case, would be new singleton cluster.
have & O(log(n/k)) at any point in time during the execution of Sparsifier.
This lemma implies that the size of the solution U C V
Deletion: When a point r is deleted from V, x is removed from each set in ...... Ug. If x is contained in some Si, then x is removed from S. and replaced with any other point currently in its cluster as the new center (if its cluster non-empty).
maintained by the algorithm is always Σ/= |S + UUr| L O(k) O(k log(n/k))-
Lemma 3.5. The solution U maintained by the algorithm Sparsifier is 4-approximate wch.p.
We refer to the above updates lazy updates. After per- forming lazy update, we have the reconstruction phase as follows.
According to Lemma 3.4 and Lemma 3.5, we can see that the solution is a (4, (t)lo(///)))aapproxiin Now, we proceed with the proof of Lemma 3.5.
as desired.
Reconstruction: For each i E [4], the algorithm periodically reconstructs layer and all subsequent layers (i.e. the sets S,,..., Sy and Us+1,..., Ut) every 1((144)) updates. To do this, for each i E [e], we keep track of the number of updates on U, after the last time it was reconstructed. After each insertion and deletion, we find the smallest index j where the number of updates on U3+1 since the last time was reconstructed is at least UUy1/4 (note that |Uyl also varies over time). See Algorithm 1 for more details. The reconstruction is done using AlvestCover in the same way as the static algorithm described above, essentially running the Mettu-Plaxter algorithm starting with the input Uy. 10 We note that, after a reconstruction, the value of e can change.
Proof of Lemma 3.5. For every C' - V, define
diam(C) == max d(z, y). a.EEC227
For each W C V and 0 < B S 1, define p (W) to be the minimum real number μ > 0 such that there exist k disjoint subsets C1 C2 Ck C W, such that
Σ |C 8- B-IW| and vi [k], (C;) S p. iE[A]
We start with a series of claims. Claim 3.6. We have vV(V) S OV).
Proof. Consider an optimal solution S S V for k-center V and the clusters C1, C2...... Ck corresponding the centers $1, : Sk in S* For each i E [k] and each v.Y C. we have d(xr, v) S d(ær, 8s) + ddss. y) S 2
Algorithm 1 Reconst
1: for = to l do
2: COUNT]E] COUNT|I] +1
3: end for
(V), Hence, diam(C.) I 2 OPT (V) for each i E ......,o C2 is partition of V, all the conditions in the definition of p1 (V) are satisfied, which concludes (L( S 2- OPT (V).
4: j smallest index s.t. COUNTIi 2 |0,1/4
[k]. Since Ci....,
5: for to do
6: COUNT]]] 0
7: end for
8: repeat
Claim 3.7. For every W CV, we have (g) S p4
9: for = 1 to M Ollogn) do
10: (Am; Bm) AlmostCover(U
Proof. For every collection of subsets {Ci of V sat- isfying the conditions in the definition of (V),,, the col- lection {Oa n W WheR satisfy the same conditions in the definition of (W). Hence, 1 (W) S (V)...
11: end for
12:
m² < arg minismmmma Am Uj} \ Bm) (S,, t (Am-; B
13:
14:
j=j+1
Claim 3.8. For every W and W satisfying IW WWI < [W]/4, we have Ph 1/2 (W") S (W).
15: until |Uy] S 16k
16:
{=j
17:
Proof. Let n² = 1 (W) and assume (Cthers) is the optimal collection in the definition of (W) such that diam (C.) S n² for all i E [k.. Define C/ == C, n W for each i [k). We show that (Chee satisfy the condi- 1/2 (W'). Obviously, diam(C)) tions in the definition of ju
1. APPROXIMATION RATIO ANALYSIS
We show the solution maintained by the Sparsifier (4, Ollg(n// kk)) approximate.
diam (C; (''W") S diam C.) S n², Since (Ca)eej)) is par- titioning of W, we have UlE C/I = [UUeee) C.)
Lemma 3.4 (Lemma 3.2, (Bhattacharya et al., 2023a)). We
For example, after reconstructing layer the outputs of the dynamic algorithm and the Metu-Plaxom algorithm are the same.
"I [C] = 1, simply define diam(C)
7

---

Almost Optimal Fully Dynamic &-Center Clustcring with Recourse
W n W |W//2. The last inequality follows from W + W' S W1/4 and a simple counting argument. n
-| (( 1)/4 + p)
This concludes p p (1 (1-22 2e 200-2211000
1)/3 = -1 92().
Claim 3.9. Consider a single call to AlmostCovez(W))
where 5 _ Wi is sampled and the balls around S of radius r cover C such that C [W1/4. Then, with constant probability, we have r S Ph (W).
Now, we are ready to complete the proof of Lemma 3.5. Consider that Vnew is the current dynamic space, and let Vaew be arbitrary. We show that d(xr, U) v 4- 4 (O (V*T"), where U is the current output of the Sparsi fier, which completes the proof. Let i* E [E] be the largest index such that x E U.. (Since U1 = V this index exists). If i* = l, we obviously have x E U2 S U and d(x; = O. Now, assume i* < We use the superscripts 'new' and 'old' to indicate the status of an object at the current time, and the last time that Almost was called on U,., respectively. For instance, the output of the last call Almost Cover on U.- equals (Sph), Upld (C).
Proof. Assume μ²= = p (W). It is sufficient to show that with constant probability, we have (B(S,,")) 2 |W1/4 (or p²) C. equivalently). Let [Ci)ve[M) be the / (W), which means dC, S 14* for i E [k]. Let X; be the in- dicator random variable for 5 in C; * 0. According to the uniform sampling from W. the probability that a point is sampled from C. equals a; == |Cll/WW] Hence, Pr(X; 1] = 1 (1 as) If there is point sam- pled from C. (i.e. X, 1). then all of the points in C2 have a distance of at most μ² from the sampled point since dCa S μ², Hence.
optimal collection in the definition of 1%
According to the definition of 1", We have that a was not removed from the space between times old and new, as oth- erwise, x became part of U1+41 and was not removed from Up until the next call to AlmostCover(U:.) which is a contradiction. We also have I E C, otherwise, would be inside U Hence, when we sampled points of Sy x must have been assigned to the growing ball around some point E Spld which we denote by B C C. Note that during the updates between old and new, the center s E B might have been swapped with another point s' E B (Since xr was never removed from B, the ball B never be- came empty and the algorithm maintains at least one point s E Spew as a representative for B). As result, there exists s E Snow such that
B B|B(S,
Σ
C Pr[X, = 1]
2 W Σ
ay (1 - (1 - ac))
1=1
Note that 2 Σ
1= 0; 2 1/2. The above function takes its
minimum when 1/k 2 0 02
ax 2 1/(2k). 12
Thus,
d(x, S d(z, 3) + d(s, 5') 2 2.kk
1/2 (U ).
(I)
E 21 W Σ as (1- (1 az) (s1)
The last inequality follows w.h.p. according to Claim 3.9 and the fact that we made O(log n) independent calls to Almost LamossCoverrUPPS (U:gl) and select the best between all (see Lines 9 to 13 in Algorithm 1). Finally, we conclude
2 W - (L/2) - (1 (1-(( (1 11/(2k)) 1
1 1- e- 1/2
>
[W].
2
d(x, U) S d(z, ST.TM) S d(x,,')
Now, since we know that 0 < IB(S < [W) we
S 2 M 1/2 (U,h))))) 22
1 2 11 (1
can conclude that with a constant probability we have (B(S, Z W41/4. More precisely, assume p Pr[[B(S, Z WW/4], then we have
S 2 1 (V ) I 4 OPT (V.ON))
The first inequality follows since ST U. the second one follows since s' E Spew the third one follows from Equa- tion (I), the fourth one follow from Claim 3.8 for W = Upe
1 1/e
W < B(S,
= Σ
Br( --
2
t=
and W -Upld (note that |Upl $ UTee < COUNT[F*] <
nn I/4), the fifth one follows from Claim 3.7, and the last one follows from Claim 3.6. As a result, w.h.p., we have d(x; U) < 4- OPT&(V nen
Σ
(= 4 WW//
|W|
Σ
Pril((S =t [W]
3.3.2. RECOURSE ANALYSIS
WII
In this section, we prove the following lemma, which sum- marizes the recourse guarantee of the Sparsi fier..
This can be simply verified by elementary calculus.
8

---

Almost Optimal Fully Dynamic &- c-Center Clustcring with Recourse
Lemma 3.10. The amortized recourse of the algorithm Sparsi fier is constant.
size of Uę after each reconstruction is at least 16k (3/4) 12k. Now, during a sequence of at most [Ue]/4 updates
before the next reconstruction from some layer j S l, the
The recourse caused by lazily updating the set U after an insertion or deletion is at most ((1) since only (1) many points are added or removed from each set. We now bound the recourse caused by periodically reconstructing the layers by using a charging scheme, similar to the one used by (Bhattacharya et al., 2023a) to bound the update time of this algorithm. Let 01,.... , or denote sequence of updates handled by the algorithm. Each time the algorithm performs reconstruction starting from layer i, we charge the recourse caused by this update to the updates that have occurred since the last time that Uj was reconstructed. If the recourse caused by this update is q, and updates have occurred since the last time that U, was reconstructed, then each of these updates receives a charge of q/p. We denote the total charge assigned the update oe by &.- We can see that the amortized recourse of our algorithm is at most (L/T) > 2r. We now show that, for each t E [7]. $ (11), implying that the amortized recourse is O(1).
size of Ug reduces to at most 12k (3/4) = 9/ (even if all of the updates are deletions). Hence, we always have
Uvl 2 9k. Now, by Lemma 3.11, it follows that |Ug] 2 |Ur|((1 - e)c-5 2 9k/(1- [[]1-----
6- s0
8
k
2,
2 O(1)
log
Us
8
c)
9
M O(1)
log
9
(1-e)e-)
1=1
I 0(1)
Σ
(1
c) (1--))-(e-iie -i+1)
s 0(1) Σ ((+1)(1 - c) 00));
-=
where the second inequality follows from the fact that f(z) := log(z)/> x is decreasing for all 2 e and the last inequality follows from the fact that -)= + 1)(1 c) is convergent series.
Consider some update o, and let U1.... U2 denote the sets maintained by the algorithm during this update. The following claim shows that the sizes of the sets U, decay exponentially,
3.3.3. UPDATE TIME ANALYSIS Lemma 3.13. The amortized update time of the algorithm Sparsifier is O(k log" n).
Lemma 3.11 (Lemma 1.1, (Bhattacharya et al., 2023a)).
There exists constant E E (0, 1) such that, for all i [f].
we have that (U|] S (1 - (1-c)-=i [Ug]-
Claim 3.12. The recourse caused by the next reconstruction of layer i is Olk lo)((..)/k:))
Proof. The subroutine AlmostCover(( can be imple- mented in 0([S)- (TT) = O(k -UT) time since we sam- ple |S] O(k) centers, and compute the distance of any point p E U to S in order to find C. Now, fix an index i E [e - 1]. Each time that the algorithm re- constructs U++1, O(log n) independent calls are made to A (mvosCCovrrUG) Hence, the time consumed for recon- struction of U4+1 is at most O . |U&| log n). Since the Sparsifier reconstructs U whenever COUNT[(] 2 |U//2 and then reset COUNT(R] to zero, we conclude that the amortized running time of all calls to A most (U,) throughout the entire algorithm is O(k log n)). Now, since f = Olog((n/ (k/k) (according to Lemma 3.4), the amortized update time of the Sparsi i fier is at most O (f-k-llgg) Ol log" n).
Proof. We first note that the size of set U, changes by at most constant factor before it is reconstructed. Since each Uj has size Okk) the recourse caused by reconstruct- ing Ug after the call to AlmostCovers
is at most (k{(E - + 1))- Since the sizes of the sets decrease ex- ponentially by Lemma 3.11, and [Up] = @(k)), it follows that é ([lo((UU./k)). Hence, the total recourse is Okk lo)lk()))))
Since the size of a set Ug changes by at most a constant factor, we know that the recourse from reconstructing U, is charged to ((Ul)) many updates. Hence, by Claim 3.12, the recourse charged to a, from this reconstruction is Ok Log((U,/k))/(U:)) Consequently, we can upper bound the total recourse charged to oe by
Conclusions and Future Work
U. 1:
We present a simple and almost optimal algorithm for dy- namic k-center answering positively open questions in pre- vious work. Natural future directions are improving the approximation factor, the recourse and the running time of our algorithm, or extending our results in the presence of outliers.
Φ
log
1=1
The size of the set U2 is always at least 9k. This is because Almost Covert(U reduces the size of U by a quarter, and combining with the condition Line 15 in Algorithm 1, the

---

Almost Optimal Fully Dynamic &- s-Center Clustcring with Recourse
Acknowledgments
Bhattacharya, S., Costa, M., Garg, N., Lattanzi, S., and Parotsidis, N. Fully dynamic k-clustering with fast update time and small recourse. In 65th IEEE Symposium Foundations of Computer Science (FOCS). 2024a.
Martín Costa is supported by a Google PhD Fellowship.
Impact Statement
Bhattacharya, S., Goranci. G., Jiang, S. H.-C., Qian, Y., and Zhang, Dynamic facility location in high dimensional euclidean spaces. In Forty-first International Conference Machine Learning. 2024b.
This paper presents work whose goal is to advance the field of Machine Learning. The nature of our work is mainly theoretical, and thus our insights might find use in various areas.
Bhattacharya, S., Costa, M., and Farokhnejad, E. Fully dynamic k-median with near-optimal update time and recourse. In 57th Annual ACM Symposium on Theory of Computing (STOC), 2025. (to appear).
References
Ahmadian, S., Norouzi-Fard A., Svensson, O., and Ward, Better guarantees for k-means and euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, 49(4):FOCS17797, 2019.
Biabani, L., Hennes, A., Monemizadeh, M., and Schmidt, M. Faster query times for fully dynamic k-center clus- tering with outliers. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural In- formation Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Ailon, N., Jaiswal, R., and Monteleoni, C. Streaming k- means approximation. Advances in neural information processing systems, 22, 2009.
Bateni, M., Esfandiari, H., Fichtenberger, H., Henzinger, M., Jayaram, R., Mirrokni, V., and Wiese, A. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In Proceedings of the 2023 ACM-SIAM Sym- posium Discrete Algorithms (SODA). pp. 2677-2727. SIAM, 2023.
Borassi, M., Epasto, A., Lattanzi, S., Vassilvitskii, S., and Zadimoghaddam, M. Sliding window algorithms for k- clustering problems. Advances in Neural Information Processing Systems, 13:8716-8727, 2020.
Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., and Trinh, K. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Transactions Algorithms (TALG), 13(2):1-31,2011
Behnezhad, S., Derakhshan, M., Hajiaghayi, M., Stein, C.,
and Sudan, M. Fully dynamic maximal independent set with polylogarithmic update time. In Zuckerman, D. (ed.), 60th IEEE Annual Symposium on Foundations of Com- puter Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pp. 382-405. IEEE Computer So- ciety, 2019.
Censor-Hilled K., Haramaty, E., and Karnin, Z. S. Optimal dynamic distributed MIS. Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL. USA, July 25-28, 2016, pp. 217-226. ACM, 2016
Bhattacharya, S., Lattanzi, S.. and Parotsidis, N. Efficient and stable fully dynamic facility location. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 Decembee 2022, 2022.
Chan, T. H., Guerquin, A., and Sozio, M. Fully dynamic k-center clustering. In Proceedings of the 2018 World Wide Web Conference on World Wide Web (WWW), pp.
579-587, ACM, 2018
Chan, T.-H. H., Guerquin, A., Hu, S., and Sozio, M. Fully dynamic k-center clustering with improved memory ef- ficiency. IEEE Transactions on Knowledge and Data Engineering, 34(7):3255-3266 2022.
Bhattacharya, S., Costa, M., Lattanzi, S., and Parotsidis, N. Fully dynamic k-clustering in Ö(k) update time. In Advances in Neural Information Processing Systems 36: Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023a.
Annual Conference
Charikar, M., Guha, S., Tardos, É., and Shmoys, D. constant-factor fonstant-factor approximation algorithm for the k-median problem. In Proceedings of the thirty-first annual ACM symposium Theory of computing, pp. 1-10, 1999.
Bhattacharya, S., Kiss, P., Saranurak, T., and Waje, D. Dy- namic matching with better-than-2 apprxxiatton in poly-
logarithmic update time. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Ital,, January 22-25, 2023, pp. 100-128. SIAM, 2023b.
Charikar, M., O'Callaghan, L., and Panigrahy, R. Better streaming algorithms for clustering problems. In Pro- ceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 30-39, 2003.
10

---

Almost Optimal Fully Dynamic &- k-Center Clustering with Recourse
Cohen-Addad, V., Hjuler, N., Parotsidis, N., Saulpic, D., and Schwiegelshohn, C. Fully dynamic consistent facility location. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 3250-3260, 2019.
Lacki, J., Haeupler, B., Grunau, C., Rozhon, V., and Ja- yaram, R. Fully dynamic consistent k-center cluster- ing. In ACM-SIAM Symposium Discrete Algorithms (SODA), 2024.
Lattanzi, S. and Vassilvitskii, S. Consistent k-clustering, In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-1 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1975-1984. PMLR, 2017.
Cruciani, E., Forster, S., Goranci, G., Nazari, Y., and Skar- latos, A. Dynamic algorithms for k-center on graphs. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms. SODA 2024, Alexandria, VA, USA, Jonuary 7-10, 2024, pp- 3441-3462. SIAM, 2024.
Mettu, R. R. and Plaxton, C. G. Optimal time bounds for approximate clustering. In Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence (UAI), pp. 344-351, 2002.
Fichtenberger, H., Lattanzi, S., Norouzi-Fard, A., and Svens- son, O. Consistent k-clustering for general metrics. In Proceedings of the 202/ ACM-SIAM Symposium on Dis- crete Algorithms, SODA 2021, Virtual Conference, Jan- uary 10 13, 2021, pp. 3660-2678. SIAM, 2021.
Pellizzoni, P., Pietracaprina, A., and Pucci, G. Fully dy- namic clustering and diversity maximization in doubling metrics. ACM Trans. Knowl. Discov. Data, 19(4), May 2025. ISSN 1556-4681.
Forster, S. and Skarlatos, A. Dynamic Consistent k-Center Clustering with Optimal Recourse. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025. (to appear).
Shindler, M., Wong, A., and Meyerson, A. Fast and ac- curate k-means for large datasets. Advances in neural information processing systems, 24, 2011.
Gan, J. and Golin, M. J. Fully dynamic k-center in low dimensions via approximate furthest neighbors. 2024
Symposium on Simplicity in Algorithms, SOSA 2024, Alexandria, VA, USA, January 8-10, 2024, pp. 269-278. SIAM, 2024.
Gonzalez, T. F. Clustering to minimize the maximum in- tercluster distance. Theor. Comput. Sci., 38:293-306 306, 1985.
Goranci, G., Henzinger, M., Leniowski, D., Schulz, C., and Svozil, A. Fully dynamic k-center clustering in low dimensional metrics. In Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2021, Virtual Conference, January 10-11, 2021, pp. 143-153. SIAM, 2021.
Henzinger, M. and Kale, S. Fully-dynamic coresets. In 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPlcs, pp. 57:1-57:21. Schloss Dagstuhl Leibnizz-Zetruu für Informatik, 2020.
Hochbaum, D. S. and Shmoys, D. B. A unified approach to approximation algorithms for bottleneck problems. ACM, 33(3):533-35 1986.
Jain, K. and Vazirani, V. V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM (JACM), 48(2):274-29) 296, 2001.

---

Almost Optimal Fully Dynamic &-Center Clustering with Recourse
A. State-of-the-Ar for Dynamic k- k-Center
Table contains a more comprehensive summary of the state-of-the-art algorithms for fully dynamic k-center in general metric spaces that we discuss in Section 1.
Table 1. State-of-the-ar for fully dynamic k-center in general metrics. We distinguish between amortized and worst-case guarantees and specify whether guarantecs hold in expectation or with high probability (when they do not hold deterministically). We also specify whether the randomized algorithms can deal with adaptive or oblivious adversaries.
Reference
Approx. Ratio
Update Time
Recourse
Adversary
(Bateni et al., 2023)
+
Ö(k/e) exp. amortized
(2(k)
oblivious
(Lacki et al., 2024)
0(1)
((poly(n)
4 worst-case
deterministic
(Forster Skarlatos, 2025)
((1)
Ö(poly(n))
2
deterministic
worst-case
(Bhattacharya et al., 2024a)
O n log w.h.p.
Ö(k) amortized
O(1) amortized
adaptive
B. A Useful Lemma
Lemma B.1. Given a metric space (V,d), an integer k & 1 and W C V, we have that OPT: S OPT)..V(
Proof. Assume U* C V is such that el(U", V) (V). For each u, U*, assume 8; E W is such that d(u, s;) d(u;, W). Let S {81,82 ..,,,,,,.................. 8.). Note that the size of S might be less than k. S is feasible solution for the k-center problem W. Fix an x E W, and let u, U* is such that d(I, u.) = d(z, U*). We have
d(x, s4) S d(x,, u.) + d(u, s.) S 2- d(z, u²) 2 d(x, U*),
where the last inequality holds by x W and the definition of s; As a result, for each W, we have Finally,
d(x,, have S 2-d(r, U*).
(P) S cl(S, W) = max d(x, < max 2 2.d(r,U* < max 2- ddxx = OPT..)( =EW
zEW
=EV
C. Improving the Recourse 8 +
In this section, we show how to use Sparsifier to obtain a new sparsifier called Buff BufferedSparsifier, that can be combined with the algorithm Dynami c-k-Cente to obtain a recourse + c for any arbitrary 0 < <c5 $ 1.
C.1. The Algorithm BufferedSparsifier
Define 4/c. We run the algorithm Sparsifier with the parameter şke, in order to maintain space W of size Ö(gk) which is a 4-approximation for OPT,,(V) with ((qk) update time. Now, we show how to maintain the output U of the bufferedSparsi fier algorithm. First, we look at the current solution W maintained by the Spars fier on the current input space V, and let = W (and save all data structures inside the Sparsi fier such as the centers the S/'s produced by internal calls to AlmostCover together with their clusters), which is 4-approximation for the (qk)-center problem on V. Then, and if point æ is removed from V and it is contained in U, we remove x and add some arbitrary point in the cluster associated with x to U (if it is not empty).
perform (q 1)k lazy updates follows. If a point is inserted into V. also insert into
After (q 1)k updates, we reset the set U, which means that we look at the current solution W maintained by the Sparsifier and let Feew = W. Now, we will remove all of the points that were previously in U and insert all of the points in new These are considered as internal updates for Dynami c-k-Center, and during these updates, we do not
12

---

Almost Optimal Fully Dynamic &-Center Clustering with Recourse
report the solution maintained by Dynamico ce ce-k-Center: We report the solution only after we have removed points of the previous U and inserted Unee_ Hence, the solution maintained by Dynamic c--CCtterr can change completely, but incur recourse of at most 2k (the previous solution was subset of size k in U and the new one is a subset of size k in ( Now, starting from this new set U we continue with lazy updates for (q 1)k many updates as described before, and this process continues.
The difference between BufferedSparsi fier and Sparsifier is that, although the recourse of Sparsi fier can is small. The reason is that we copy the solution
be a large constant, the amortized recourse of BufferedSparsiff W maintained by Sparsifier and then perform lazy updates that each lead to low recourse, for a long period of time (qq - 1)k updates). Since the copied space W is good approximation of OPT yk (V), we show that it remains good approximation for OVTx(V) during this longer period.
C.2. Analysis of BufferedSparsifiee
In order analyze the approximation guarantee of BufferedSparsi need the following lemma, known the Lazy-Updates Lemma.
Lemma C.1 (Lemma 3.3 in (Bhattacharya et al., 2024a)). Assume V and V are two subsets of a ground metric space V such that |V + V'I S s for some 2 0. Then, for every & 2 1, we have OPTR++<VV OVT,
Lemma C.2. The approximation ratio BuffereddSarsiffier is
Proof. Consider a point in time where we set U- = W (the solution maintained by the Spars i f fier). Assume V is the current input space and ~ = U. It is sufficient to show that the maintained solution U is always a 4 approximation for the k-center problem on the current space after i updates for any arbitrary S i S (q - 1)k. Fix i and let U' and V be the maintained solution and the input metric space after updates, respectively. Let := V 0 be the set of inserted points to V. Assume D 000 \ U is the set of deleted points from V that affect U, and are replaced with arbitrary points in their clusters. Hence, U U - D R + I, where R is the set of centers that are replaced with centers in D.
According to the procedure of the BufferedSparsifiet increase the cost of the solution U, i.c. cl(U", VV) S cl(U D + R, VO). According to the 4-approximation analysis for Sparsi frerrriiiirr in Section 3.3.1, whenever a point u E D is replaced with any arbitrary point within its cluster, the solution remains a 4-approximation (see the discussion at the end of Section 3.3.1). Hence, cl(U/ D + R, Vo) S 4 OPT (VV).
since every point in I is inserted into U, they do not
Combining the two previous incqualities with Lemma C.I, for every 0 S i S (g- 1)k: we have that
cI(U', V')= S cl(U' D R, VO) < 4- OPT (V") ) < 4 ,P (V') S OPT)(V").
The last inequality follows since qk - i 2 k. As a result, during the lazy updates, the bicriteria solution U is always a 4-approximation for the k-center problem on the original metric space.
Lemma C.3. The amortized recourse of the algorithm obtained by composing Dynami BufferedSparsifier is at most 8 -
with the sparsifier
Proof. During the lazy updates, for every insertion in V, we have an insertion in U, and for every deletion from V, we have at most two updates in U (deleting a center and replacing it with any arbitrary point within its cluster). Hence, the length of the input stream (updates on U) which is fed into Dynamic-k-Cert c-k-Center is most twice the length of the main input stream. We incur a recourse of at most 4 in expectation w.r.t. the input stream fed to Dynami c k- Center according to the recourse analysis of the algorithm in Section 2.3, which concludes that the total amortized recourse w.r.t. the main input stream is at most 8. After restarting U, we incur a recourse of at most 2k since we have two solutions of size k. Note that the internal changes in the main solution during deletion of points in the previous U and adding the points in the new U does not count as recourse for the final algorithm, since we only report the final solution after all of these updates as the solution by the algorithm maintained.
Since the above procedure happens only every (g 1)k updates, the total amortized recourse incurred by these updates is at most 2/(q- 1). As result, the final recourse of the algorithm is 8 + 2/(g 1) S 8 +
Remark C.4. In many worldworld applications of the k-center problem, the dynamic input space is always a subset of a static ground metric space (such as Ra the Fuclidean k-center problem), and it is allowed to open any arbitrary point from the
13

---

Almost Optimal Fully Dynamic &-Center Clustering with Recourse
ground metric space center. It is possible to tweak Bu fereeeearrssseeeee fier fier in order to provide sparsifier which is not necessarily subset of the current dynamic space V, but has the following guarantees. By feeding the output of this sparsifier into -eeraamicc-----eetee
we still have 20 approximation algorithm. The amortized recourse of the final algorithm becomes + instead of 8 + c. The tweak is simple and works as follows. Whenever a point z is removed from the space and it is contained in a S; instead of replacing x with any arbitrary point in the cluster æ, we just keep x as is. The only time that we remove I, is whenever the cluster of æ becomes empty (all of the points the cluster æ, including æ itself, are removed from the original space). With a similar argument, is possible to show that any 8-approximate solution w.r.t. U is 20-approximation solution w.r.t. the original space. The recourse of + also follows immediately with the previous arguments. As result, if we are allowed to open centers from outside the current dynamic space V, it is possible to achieve a dynamic k-center algorithm with an approximation ratio of 20 and recourse of 4 + E.
14


Reviews:
[{"review_id": "EdzSJ9UPe4", "reviewer": "Reviewer_GqKD", "summary": "There is no better summary of the paper than the one given in the abstract of the paper. So, I'll simply copy it below: \n_\"We give a simple algorithm for dynamic k-center that maintains an O(1)-approximate solution with O(1) amortized recourse and ˜O(k) amortized update time, obtaining near-optimal approximation, recourse and update time simultaneously. We obtain our result by combining a variant of the dynamic k-center algorithm of Bateni et al. [SODA’23] with the dynamic sparsifier of Bhattacharya et al. [NeurIPS’23].\"_\n\nLet me expand on some of the terms used to better understand the above statement.\n- Dynamic algorithm: The algorithm maintains a solution for the problem at every step of data update, which includes both insert and delete operations on data items.\n- The time to update the solution at every step is the update time, and the number of changes to the maintained solution is the recourse. The amortised analysis considers the overall resource usage across all steps instead of considering the worst-case over all the steps.\n\n-The k-center problem is NP-hard to approximate below 2-approximation. Given this, O(1) approximation is the best one can hope for.\n- The minimum number of steps required to obtain any constant approximation for k-center is \\Omega(nk). Given this, O(k) update time is the best one can hope for. \nSo, the result is nearly optimal in approximation factor, update time, and recourse. Previous results did not achieve these almost-optimal bounds on ALL of (approximation, update, recourse).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank all the reviewers for their efforts and insightful comments. Please let us know if you have any questions about our rebuttal.\n\nIn order to keep the proofs simple, we did not optimize the constant in the approximation ratio in the paper. By carrying out a more intricate analysis of the sparsifier, we can show that our approximation ratio is at most $20$---this is the best approximation ratio of any algorithm with constant recourse, \\emph{even if we allow exponential update time}. In particular, the previous smallest was $24$ by Lacki et al. [SODA'24].\nWe have also done some experiments and compared the approximation ratio of our algorithm with the static $2$-approximation offline greedy algorithm by Gonzalez; we observed that the quality of the solution maintained by our algorithm is significantly better than what is derived by the current analysis.\nSpecifically, we tested our dynamic algorithm on 5 different datasets, on inputs of size $n = 10000$ with $k = 10, 50$ and $100$, and compared the cost of the solution maintained by our algorithm to the cost of the solution produced by the offline greedy algorithm. We observed that the cost of the solution produced by our algorithm is consistently within a factor of 1.25 - 1.75 of the cost of the greedy algorithm.\n\nThank you for pointing out the issue with using the DynamicMIS algorithm as a black box.\nWe will elaborate on this and clarify this point.", "claims_and_evidence": "Yes, the claims made in the paper are supported by evidence.", "methods_and_evaluation_criteria": "Yes, the evaluation criteria makes sense.", "theoretical_claims": "I verified the claims at a high level, and the claims are sound. It is possible that I may have missed some specific details.", "experimental_designs_or_analyses": "This is a theoretical paper. There are no experiments.", "relation_to_broader_scientific_literature": "The paper makes non-trivial progress on a theoretical problem on dynamic k-center problem. This is an important addition to the theory of clustering.", "essential_references_not_discussed": "I found the references are appropriate.", "other_strengths_and_weaknesses": "Strengths:\n- The paper achieves almost optimal bounds for all the relevant resource bounds in a dynamic algorithm for the k-center problem (an important clustering problem).\n- This is an important progress from the theoretical viewpoint. The paper brings together several ideas from dynamic algorithms literature and utilises them to design a state-of-the-art dynamic algorithm.\n- The high-level ideas in the paper are well presented. \n\n\n\nWeaknesses: \n- It would be good to see experimental results that compare the given algorithm with other known dynamic algorithms.\n- Instead of stating O(1) approximation, it might be good to explicitly state the constant in the constant factor approximation (unless the constant is bad). If this constant equals 2, then a brief discussion on where the loss happens could help close the gap.\n- Briefly describing DynamicMIS used in Lemma 2.1 should help the reader unfamiliar with the previous literature. For example, it seems from the statement of Lemma 2.1 that DynamicMIS is a randomised algorithm (hence the expectation). So, it should be mentioned clearly that the expectation is over the internal randomness of the algorithm. This also makes is clear that the proposed algorithm is a randomised algorithm.", "other_comments_or_suggestions": "- Some comments have been mentioned in the strengths and weaknesses section.\n\n## Update after rebuttal:\nI have decided to retain my score of (4:accept) after the rebuttal.", "questions_for_authors": "- Some important questions have been mentioned in the strengths and weaknesses section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FFrAVC8baQ", "reviewer": "Reviewer_hRcL", "summary": "The paper proposes an algorithm for the k-center problem in the fully-dynamic setting in general metric spaces. In particular, the proposed method obtains a constant approximation with constant recourse and Otilde(k) update time (thus the name “almost optimal”). The algorithm is based on a combination of the reduction of the k-center problem to dynamic MIS in threshold graphs by Bateni et al. with the dynamic sparsifier (for k-median) of Bhattacharya et al.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank all the reviewers for their efforts and insightful comments. Please let us know if you have any questions about our rebuttal.\n\nOur algorithm can be implemented to have an update time of $O(k \\cdot \\log^4 n \\log \\Delta)$ by using standard data structures.\nRegarding the approximation ratio and recourse, we did not optimize our analysis of the constants in these bounds for the sake of simplicity.\nBy carrying out a more intricate analysis of the sparsifier, we can show that our approximation ratio is at most $20$---this is the best approximation ratio of any algorithm with constant recourse, even if we allow exponential update time. In particular, the previous smallest was $24$ by Lacki et al. [SODA'24].\nFurthermore, by slightly tweaking how we use the sparsifier, we can get a recourse of at most $4 + \\epsilon$, for any constant $\\epsilon > 0$ (we note that the best we can hope to achieve here is a recourse of $2$, since in the worst case we must remove a point and insert a new point).\nWe tried to keep the proofs simple and provide asymptotic bounds.\nAlthough the constants in the approximation ratio and recourse are not specified in the current analysis, they are good in practice.\n\nWe implemented our algorithm and compared the approximation ratio of our algorithm with the static $2$-approximation offline greedy algorithm by Gonzalez; we observed that the quality of the solution maintained by our algorithm is significantly better than what is derived by the current analysis.\nSpecifically, we tested our dynamic algorithm on 5 different datasets, on inputs of size $n = 10000$ with $k = 10, 50$ and $100$, and compared the cost of the solution maintained by our algorithm to the cost of the solution produced by the offline greedy algorithm. We observed that the cost of the solution produced by our algorithm is consistently within a factor of 1.25 - 1.75 of the cost of the greedy algorithm.\n\nRegarding recourse, we also observed that the amortized recourse of our algorithm is actually sublinear in practice, at most $1$ in almost all of our test results.\n\nWe will improve the accuracy of the statements in the paper and provide precise guarantees.\nWe will also improve the analysis and provide a clear road map together with a natural flow for the analysis to be easy to follow for the reader.\n\nThank you for pointing out the results that we missed mentioning in our paper.\nWe will add them to the introduction and the related work sections of our paper.\n\nRegarding the query time, note that our algorithm maintains the solution explicitly after every update.\nWithout considering an explicit solution after every update, we can not define the notion of recourse.\nIn this framework, the query time is subsumed by the update time since we can assume there is a query after every update as the solution must be maintained explicitly.\nWe will mention this clearly in the introduction to prevent any confusion.", "claims_and_evidence": "The theoretical claims seem to be correct. However, they are often very imprecise (see W1 and W2).", "methods_and_evaluation_criteria": "The proposed method, which combines two existing theoretical tools, is simple and very effective.", "theoretical_claims": "I checked the proofs, albeit not in depth, and they seem to be correct. However, they often lack clarity.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "The paper combines two existing theoretical tools from the literature in a non-trivial way. This paper represents a step forward in closing the gap towards an optimal algorithm for dynamic k-center.", "essential_references_not_discussed": "Some additional references (albeit not essential) could be discussed, see W3.", "other_strengths_and_weaknesses": "Strengths:\n- S1: the k-center problem is a highly relevant topic, and the fully dynamic framework is of great interest to both theoreticians and practitioners. \n- S2: the paper is technically very solid. the contributions, although incremental on the works on which is based, are non-trivial and seem to be correct. Moreover, the paper represents a step forward in closing the gap towards an optimal algorithm for dynamic k-center.\n\n---\n\nWeaknesses:\n- W1 (Main concern): Hiding the logarithmic factors in the $\\widetilde{O}$ notation is fine for the statements in the introduction. However, in the rest of the paper, the correct asymptotic running time should be stated. Indeed, the current notation would make it harder for subsequent works to compare the running times to the ones of the present work (e.g. the comparison for reasonable values of $k$ between a $O(k \\sqrt k)$ algorithm and a $O(k  (\\log k)^{10} )$ algorithm would be misrepresented by the $\\widetilde{O}$ notation.) \nThe same actually holds for the approximation ratio and recourse, they should be clearly stated in the theorem statements in the technical sections. I would say this is especially important in a venue like ICML, which is of interest also to practitioners (unlike STOC or FOCS). \n- W2: the fact that the algorithm assumes oblivious adversaries, although fair, should be stated in Theorem 1.1, as not to overstate results. It is unclear to me why the authors chose to duplicate the theorem into Thm 1.1 and 1.3. \n- W3: The discussion of related works seems insufficient, as it fails to discuss related works such as:\n    * [1] improves memory requirements over the original fully dynamic k-center paper, at the cost of a worse approx. ratio.  \n    * [2] 2+eps in general metric spaces, efficient in spaces with low doubling dimension.\n    * [3] 2+eps in general metric spaces, state-of-the-art for update times in spaces with low doubling dimension. Also, k and eps are not needed to be known in advance, which offers an advantage over the present work. \n    * [4] 2+eps approximation, and offers an alternative approach for spaces with low doubling dimension. Also does not require k and eps to be known. \n    * [5] proposes an algorithm for dynamic k-center on graphs. \n\nThese works and the relationship to the present work should be discussed in the related work section or in Table 1. See for example Table 1 in [4]. \n\n- W4: The proofs, albeit correct, are not easy to follow, as they require jumping back and forth in the paper. As an example, the recourse analysis in Thm 1.3 is proved for the sparsifier in Section 3.4.2, but then requires the reader to backtrack to Lemma 3.3 to recall how this is used to obtain the total recourse. A few sentences here and there to guide the reader would go a long way. \n- W5: As previously stated, the paper is incremental with respect to the works on which is based. Indeed, other than combining the two established techniques, it seems like the recourse analysis of the sparsifier is the only substantial technical contribution. \n\n---\n- [1] Chan, T-H. Hubert, et al. \"Fully Dynamic k-Center Clustering With Improved Memory Efficiency.\" IEEE Transactions on Knowledge and Data Engineering (2020).\n- [2] Goranci, Gramoz, et al. \"Fully dynamic k-center clustering in low dimensional metrics.\" 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). \n- [3] Pellizzoni, Paolo, Andrea Pietracaprina, and Geppino Pucci. \"Fully dynamic clustering and diversity maximization in doubling metrics.\" Algorithms and Data Structures Symposium. 2023.\n- [4] Gan, Jinxiang, and Mordecai J. Golin. \"Fully dynamic k-center in low dimensions via approximate furthest neighbors.\" Symposium on Simplicity in Algorithms (SOSA) 2024\n- [5] Cruciani, Emilio, et al. \"Dynamic algorithms for 𝑘-center on graphs.\" arXiv preprint arXiv:2307.15557 (2023).", "other_comments_or_suggestions": "Minor comments:\n- You state that the fully-dynamic framework focuses mainly on the three metrics, approximation ratio, recourse and update time. This is a compelling story for your paper. However, I would argue that there is a fourth metric, the query time. This is arguably the most important one. Saving all the points in a set and re-running Gonzalez on the pointset after each update has very low update time and yields the optimal approximation guarantee, but of course it has terrible query time, and thus does not qualify as a fully dynamic algorithm. This should be mentioned at least briefly. \n\n\nRemark: Despite the simplicity of the proposed method, I am prone to suggesting acceptance if the authors address (e.g. by stating clearly the modifications they would make to the manuscript) my concerns on (i) the clarity in the statements of the theorems, and also on (ii) the literature review and (iii) the clarity of proofs.\n\nEdit: after the rebuttal, I increased my score to suggest acceptance.", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U6lLE6mrGZ", "reviewer": "Reviewer_342V", "summary": "This paper gives almost optimal dynamic $k$-center algorithm in metric space. In dynamic $k$-center, the task is to obtain an approximate solution with as small update time and recourse, where recourse means the number of center points needed to be updated per insertion/deletion. \n\nThis paper designs an algorithm to obtain $O(1)$-approximation with $\\tilde{O}(k)$ update time and $O(1)$ recourse. So it achieves improved or matching guarantees in all metrics (approximation factor, update time, recourse) upon all existing results. This is impressive.\n\nTechnically, authors borrow a few techniques from the literature and manage to combine all the advantages.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank all the reviewers for their efforts and insightful comments. Please let us know if you have any questions about our rebuttal.\n\nIt is known that an update time of $\\Omega(k)$ is necessary for this problem.\nAs stated in Line 58 in the introduction, it is known that, in the static setting, a running time of $\\Omega(nk)$ is necessary to achieve any non-trivial approximation (Bateni et al. 2023).\nAny dynamic algorithm with $o(k)$ update time yields a static algorithm with $o(nk)$ running time, which rules out any non-trivial approximation ratio.\nHence, $\\Omega(k)$ update time is necessary in the dynamic setting, which means that $\\tilde{O}(k)$ update time is near optimal (up to polylog factors).\n\nIndeed, when we say that our algorithm succeeds with high probability at every update, we mean that the approximation ratio holds with high probability after handling each update (please see Footnote 5 in Theorem 1.3).", "claims_and_evidence": "The claims have been proved rigorously.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I read the proofs and I think they are correct.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "Dynamic k-center is an important research problem in algorihtmic machine learning. This paper achieves state-of-the-art dynamic k-center algorithm. I believe the result will benefit future research.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength: 1. The algorithm presented is easy to follow. 2. The paper is mostly written well.\n\nWeakness: No experiments.", "other_comments_or_suggestions": "I have not found typos. The writing is very good.", "questions_for_authors": "1. Are there any evidences (e.g. a lower bound) that $\\tilde{O}(k)$ is a necessary update time bound?\n2. Which metric of the algorithm performance suffers failure probability? I have not found the explicit probability claim in Theorem 1.1. Is it the case that with high probability the algorithm succeeds at every update?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MsgdYXqDEh", "reviewer": "Reviewer_WqgH", "summary": "The paper claims to construct an $O(1)$-approximate solution for the metric $k$-center problem in the dynamic setting, with $O(1)$ amortized recourse and $\\widetilde{O}(k)$ amortized update time. By combining a recursively nested MIS (Maximal Independent Set) with a dynamic sparsifier, the paper improves the amortized update time of MIS from $\\widetilde{O}(n)$ to $\\widetilde{O}(k)$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank all the reviewers for their efforts and insightful comments. Please let us know if you have any questions about our rebuttal.\n\nThank you for pointing this out; this will help us improve the clarity of the proofs.\nIndeed, since $\\beta = O(\\log (n/k))$,\nthere is a $\\log (n/k)$ factor hidden in  $\\Tilde{O}(k) = O(k \\cdot \\log (n/k))$, which also adhere our use of notation $\\Tilde{O}$ (please see footnote $2$ in page $2$).\nWe will point this out clearly in the Notation section instead of the footnote.\nNote that this will not break down the proof of Theorem 1.3 since no matter what is the size of the space (either $n$ before using sparsifier, or $\\beta \\cdot k = k \\log (n/k)$ after using sparsifier) the recourse would be constant since we are calling the algorithm of Theorem 1.2 on this space which has constant recourse (i.e. $R_A(\\cdot) = O(1)$ in Line 312).\n\nYou are right about the comment on page 8. There is a typo in Line 435, we should have written: ``each $S_j$ has size $O(k)$\".\nThe rest of the analysis remains intact and correct.\nDue to space constraints, we could not elaborate more on the proofs in the paper.\nBelow, we explain the proof in more detail (note that the current proof in the paper is self-contained and this explanation does not add any new ideas or change the proof):\n\nClarification on the proof:\nNote that the recourse is defined as the number of changes in the output of the sparsifier $U = S_1 \\cup S_2 \\cup \\cdots \\cup S_{\\ell-1} \\cup U_\\ell$ (see line 13 of Algorithm 1), and by reconstructing from $U_i$, the sets undergoing changes in the output are $S_i, S_{i+1}, \\ldots, S_{\\ell-1}$ and $U_\\ell$.\nThis concludes the total change in the output $U$ is at most $O(k(\\ell-i+1))$ since each $S_j$ has size $O(k)$, as well as $U_\\ell$.\nAlthough $|U_1| = O(n)$, the sizes of $U_i$s decrease \\textbf{exponentially} according to Lemma 3.11, which is the key fact that we use to bound the recourse.\n\nThe recourse caused by reconstructing from $U_i$ is at most $O(k(\\ell-i+1))$ as explained above.\nSince the sizes of $U_i$s decrease exponentially (according to Lemma 3.11) until it becomes $|U_\\ell| = \\Theta(k)$, we get $\\ell - i = O(\\log(|U_i|/k))$.\nSince we only start the reconstruction from $U_i$ every $\\Omega(|U_i|)$ steps, the amortized recourse incurred by all the reconstructions starting from level $i$ would be bounded by $\\frac{k}{|U_i|} \\cdot \\log \\left( \\frac{|U_i|}{k} \\right)$.\nThe rest of the analysis follows from the bound on the potential function defined in the paper.", "claims_and_evidence": "The proofs for MIS are clear and convincing. However, the explanation of the dynamic sparsifier lacks clarity; more details or a refined lemma for the properties of the dynamic sparsifier may be useful.", "methods_and_evaluation_criteria": "The methods are appropriate. The paper adapts the dynamic sparsifier from $k$-means to $k$-center via a conversion from $k$-means to $(k,p)$-clustering and then to $k$-center.", "theoretical_claims": "The proofs and analysis for MIS are correct. However, the analysis of amortized recourse and update time in the dynamic sparsifier is unclear and raises questions:\n1) In the expression \"$\\beta · k = \\wiletilde{O}(k)$,\" is a $\\log n$ factor hidden?\n2) On page 8, the paper states that \"each $U_j$ has size $O(k)$.\" However, since $U_1 = O(n)$, could $U_j$ potentially be $O(n)$? If so, should the recourse here include a $\\log n$ term?", "experimental_designs_or_analyses": "No experiments are included.", "relation_to_broader_scientific_literature": "The paper claims to achieve optimal approximation ratio, amortized recourse, and update time simultaneously, building on prior work.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The work demonstrates originality by extending the dynamic sparsifier from $k$-means to $k$-center. The notation and lemmas are clearly presented, and the proof ideas are straightforward.", "other_comments_or_suggestions": "No", "questions_for_authors": "Mentioned above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethics_expertise_needed": ["Other expertise"]}}]

Author rebuttal:

Meta-review: The paper presents a simple algorithm for the dynamic $k$-center problem that achieves a constant-factor approximation, $O(1)$ amortized recourse, and $\tilde{O}(k)$ amortized update time, matching near-optimal bounds across all three measures. Although the results are qualitatively meaningful, the two main initial areas of concern stemmed around
- Imprecise guarantees for approximation, hidden in $O(1)$ notation
- Lack of experiments

As the focus of the paper is theoretical, the lack of experiments is not crucial. Moreover, the author response clarified the precise terms in the $O(1)$ notation, thereby resolving the initial reviewer concerns, provided these changes are reflected in future versions.
Decision: Accept (poster)