Competitively Consistent Clustering
Authors: Niv Buchbinder
Roie Levin
Yue Yang
Venue: ICML 2025 poster (2025)
Keywords: Online Algorithms
Recourse
Clustering
k-center
Facility Location
k-median
Primary area: theory->optimization
TL;DR: We give the first algorithms for clustering dynamically changing datasets that are competitive both in terms of the clustering quality, and in terms of the consistency (i.e. how much the solution changes over time).

Abstract: In *fully-dynamic consistent clustering*, we are given a finite metric space $(M,d)$, and a set $F\subseteq M$ of possible locations for opening centers. Data points arrive and depart, and the goal is to maintain an approximately optimal clustering solution at all times while minimizing the *recourse*, the total number of additions/deletions of centers over time. Specifically, we study fully dynamic versions of the classical $k$-center, facility location, and $k$-median problems. We design algorithms that, given a parameter $\beta\geq 1$, maintain an $O(\beta)$-approximate solution at all times, and whose total recourse is bounded by $O(\log |F| \log \Delta) \cdot OPT_{rec}^{\beta}$. Here $OPT_{rec}^{\beta}$ is the minimal recourse of an offline algorithm that maintains a $\beta$-approximate solution at all times, and $\Delta$ is the metric aspect ratio. We obtain our results via a reduction to the recently proposed *Positive Body Chasing* framework of [Bhattacharya Buchbinder Levin Saranurak, FOCS 2023], which we show gives fractional solutions to our clustering problems online. Our contribution is to round these fractional solutions while preserving the approximation and recourse guarantees. We complement our positive results with logarithmic lower bounds which show that our bounds are nearly tight.

Competitively Consistent Clustering
Niv Buchbinder'
Roie Levin" 2 Yue Yang"
2
Abstract
dataset in metric space, the task is output a set of cluster centers that minimize an objective which is function of the distances between data points and their nearest center. In this work we study three such clustering formulations: (i) k-center, in which we can open at most l centers and we seek to minimize the maximum distance of any point to its nearest open center, facility location, in which there is cost open each center, and we wish to minimize the sum of opening costs plus the sum of distances between each data points and its nearest open center, and (iii) k- median, in which we can open at most & centers, and we wish to minimize the sum of distances between each data point and its nearest open center. These classical objectives have been studied extensively for the last few decades, and though they are NP-hard, their approximability is almost completely understood (Byrka et al., 2017; Byrka & Aardal, 2010; Jain et al., 2002; Hochbaum & Shmoys, 1986; Guha & Khuller, 1999).
In fully-dynamic consistent clustering, we are given a finite metric space (M, d), and a set F C M of possible locations for opening centers. Data points arrive and depart, and the goal is to maintain approximately optimal clustering so- lution at all times while minimizing the recourse, the total number of additionss/eletions of centers over time. Specifically, we study fully dynamic versions of the classical k-center, facility location, and k-median problems. We design algorithms that, given a parameter /3 2 1, maintain an (3)- approximate solution all times, and whose total recourse is bounded by Oloo [F] log ---OPTR Ruc- Here OPTRR is the minimal recourse of an offline algorithm that maintains a -aapproximate solution at all times, and A is the metric aspect ratio. Fi- nally, while we compare the performance of our algorithms to an optimal solution that maintains k centers, our algorithms are allowed to use slightly more than A centers. We obtain our results via a reduction to the recently proposed Positive Body Chasing framework of [Bhattacharya, Buchbinder. Levin, Saranurak, FOCS 2023], which we show gives fractional solutions to clustering prob- lems online. Our contribution is to round these fractional solutions while preserving the approxi- mation and recourse guarantees. We complement our positive results with logarithmic lower bounds which show that our bounds are nearly tight.
In practice however, we are often faced with situations where the data is not static but evolving over time. As the data change, may be important to maintain set of cluster centers that not only minimizes the objective at hand, but also does not change drastically between time steps. For example, suppose we clustering as a preprocessing step to split data among servers; shuffling data between servers with every update could be prohibitively costly. This harder task, known as consistent clustering, is less well understood than its offline counterpart and has drawn sig- nificant attention in recent years from both academic and industry researchers (Lattanzi & Vassilvitskii, 2017; Cohen- Addad et al., 2022; 2019; Chan et al., 2024; Bhattacharya et al., 2022a; Fichtenberger et al., 2021; Eącki et al., 2024; Guo et al., 2021; 2020; Moseley et al., 2023; Bhattacharya et al., 2024b; Forster & Skarlatos, 2025; Bhattacharya et al., 2024a).
1. Introduction
Clustering is a fundamental optimization primitive and one of the most widely used tools in data analysis. Given a
To the best of our knowledge, all state-of-the-art fully- dynamic consistent clustering results aim for absolute re- course bounds. These are guarantees of the form "After T data point insertions or deletions, the algorithm incurs at most c- ' recourse." " Consider, for example, the recent work of Lącki at el. (łąçki et al., 2024) which gives an algorithm for fully-dynamic k-center that maintains constant approx- imation with O(T') recourse. This highly non-trivial bound is significant improvement over previous results (Lattanzi
AAtthors ordered alphabetically. 'Department of Statistics and Operations Research, School of Mathematical Sciences, Tel Aviv University, Israel. *Department of Computer Science, Rutgers University, Piscataway, NJ 08854. Correspondence to: Niv Buchbinder <mivbuuchbinder@e com,, Roie Levin levin rutgers.edu>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Competitively Consistent Clustering
& Vassilvitskii, 2017; Fichtenberger et al., 2021); it is also
incurs recourse at most O ( log [F] log A) OPT
best possible in the sense that there exist update sequences for which o(T) recourse does not suffice to maintain con- stant approximation.
for facility location that maintains an 0(3)- approximate solution and incurs recourse most Ollog [F] log A) OPT
However, these sequences in which every algorithm incurs ((T) recourse seem pathological and unrealistic: for ex- ample, if a set of k + 1 points that are far from each other depart then return repeatedly in round-robin fashion, any good k-clustering approximation algorithm must open and close center at every time step. In fact, low-recourse clus- tering makes the most sense as a goal when the data has consistent structure over time, i.e. precisely when there exists an offline solution that rarely change its centers over time.' In recent work, (Bhattacharya et al., 2023) initiated the study of algorithms with competitive recourse, which have refined guarantees of the form "Over the course of the input sequence, the algorithm incurs recourse that is at most c OPTREC." Here OPTREC which is the minimal recourse of any offline algorithm with full foreknowledge of the input that maintains an optimal solution at all times. More generally, for any B 2 1, they compare the online algorithm's recourse to OPT REC. which is the optimal re- course of an offline algorithm that is allowed maintain 8-approximate solution at all times.? To rephrase in this language, we claim that for realistic instances of consistent clustering and reasonable constant values of B, we have OPT REC << T.3
for k-median that maintains an ((3) -apprxxaaee so- lution, uses (kk centers, and incurs recourse at most O(log [F] log A) OPT RuC
Here A is the aspect ratio of the metric space, and F is the set of locations where the algorithm can open a center.
We complement our upper bounds by showing that least one logarithmic factor is unavoidable.
Theorem 1.2 (Lower Bound). Suppose there is random- ized algorithm that given a parameter B 2 1 as an input maintains an (ax -ppprooxxiiatoon for one of fully-dynamic facility location, k-center, or k-median. Then this algorithm has recourse at least (min(log [F), log, }}- S-OPTREC For k-center and k-median, the lower bound holds even if the algorithm allowed open O(k) facilities.
Finally, we evaluate our three clustering algorithms experi- mentally on UCI Machine Learning repository datasets. Our experiments demonstrate not only that our algorithms are simple to implement in practice, but that they also signifi- cantly outperforms the worst-case bound predicted by the theorem. They also seem to show that OPT < T we predict.
1.1. Results
In this work we initiate the study of consistent clustering algorithms in the fully dynamic model with competitive re- course. We study fully dynamic versions of three classical clustering problems, the ke-cente problem, the facility lo- cation, and the k-median problem. Our main result is the following.
1.2. Techniques and overview
The starting point of our work is the positive body chasing framework of (Bhattacharya et al., 2023). Loosely speak- ing, they show that given a sequence of convex bodies K K2..... Ky revealed online, when these bodies are defined by packing and covering constraints, there is an algorithm that maintains a point x'' E K, online such that the total & movement Σ, || x'11111 (or "fractional re- course") " is within logarithmic factor of OPTREC, the mini- mum fractional recourse of an offline algorithm maintaining point in the same bodies. In Appendix A show how to cast suitable fractional version of our three dynamic clustering problems as positive body chasing.
Theorem 1.1 (Upper Bound). For every 3 2 1, there exists a dynamic clustering algorithm
for k-center that given an e E (0, 1/2) maintains an 0 apprrxiiieeee solution, uses (1+c). k centers and
'This is reminiscent of (Awasthi et al., 2012) which gives poly- nomial time algorithms for clustering instances whose solutions are stable under perturbations. They posit that these are inputs one would realistically want to cluster in the first place.
The main contribution of our work is to show how to round the fractional solution output by (Bhattacharya et al., 2023) while preserving both recourse and approximation guaran- tees. Offline, rounding is already a non-trivial task tailored for each problem separately. Online, rounding imposes ad- ditional challenges: not only should the integral solution preserve feasibility and the objective function value, but it should also maintain a stable solution over time. The latter property does not hold for most textbook rounding tech- niques, for which a small change in the fractional solution
Note that the value OPT by definition, decreases as i9 in- creases. For the k-center objective, the proof (L.ckk et al., 2024) shows that there is setting of 3 = 0(1) such that OPT = O(T).
We note that (Fichtenberger et al., 2021) can be interpreted competitive recourse guarantce, but this result is only for the incremental setting. They show Ō(k) absolute recourse algorithm, which is also poly log competitive because & is lower bound on the recourse of any algorithm opening & centers.
2

---

Competitively Consistent Clustering
may result in large changes to the rounded integral solution. To this end, various online rounding ideas were proposed in the context of other problems (Alon et al., 2009; Bansal et al., 2012; Adamaszek et al., 2012; Bansal et al., 2011; Krishnaswamy et al., 2023).
course this change. Otherwise, we show via potential function argument (and set of invariants) how to bound the number of balls we drop. Our k-median rounding al- gorithm, which we discuss in Section 3.3, turns out to be a direct consequence of the result in Section 3.2. In Sec- tion 4, we evaluate implementations of all our algorithms experimentally.
In Section 3.1 we design a rounding algorithm for the k- center problem. It well known that the greedy algorithm that repeatedly adds to the solution any point farther than
In Appendix C we show our logarithmic lower bounds that draws ideas from the lower bound in (Fotakis, 2008). The lower bound holds even against fractional algorithms (and hence also randomized algorithmm). For all three problems, we use variants of a uniform binary HST metric, and the request sequence inserts clients along a root to leaf path. The adversary adaptively picks this path such that the next request falls in a subtree with very few open centers, frac- tionally. The nature of the metric ensures that the algo- rithm must move fractional mass into this subtree if it wants to maintain a good approximation, thus incurring high re- course.
OPT (for 2 2) to an open center opens most k centers, and hence is a a-approximation (Gonzalez, 1985). Can we emulate this strategy in the dynamic setting using the fractional solution as our guide? When the maximum intracluster distance OPT does not change, the LP guaran- tees that every new center OPT far from an open center has an LP mass of 1 lying in the ball of radius OPT around it. If we run the greedy algorithm and, the fractional solu- tion moves, we also drop centers whose ball's mass dips significantly below 1, then we can charge the recourse of the center leaving the solution to the & movement of the fractional solution that caused the dip.
1.3. Additional related work
The story is more involved in the general case when the value of OPT changes over time. When the value of OPT changes, the strategy above may drop balls despite the frac- tional solution not moving at all, and hence a more careful argument is required. In particular, we would like our al- gorithm to be "lazy" and only move centers when it has no other choice. Our algorithm actively maintains a set of "well separated" balls of different radii around its chosen cluster centers, and uses a potential function argument (and set of invariants) to bound the number of balls we drop before the solution reaches feasibility. Intuitively, whenever we drop ball and the fractional solution does not change enough, we show that a new ball that is added has a much smaller radii compared with the ball we dropped, and this can only happen Ollog A) many times.
Clustering under various objectives is by now classic prob- lem with many known approximation algorithms. We men- tioned a few besides those included in the introduction (Arya et al., 2004; Kanungo et al., 2004; Jain et al., 2003; Charikar & Guha, 2005), but for a more complete treatment, see the relevant sections of (Williamson & Shmoys, 2011).
Besides the stable clustering algorithms mentioned above, there is a well-established line of work on low-recourse dy- namic algorithms for a host of combinatorial problems, e.g. Steiner tree (Imase & Waxman, 1991; Gu et al., 2016; Gupta & Kumar, 2014; Eącki et al., 2015; Gupta & Levin, 2020), load balancing (Awerbuch et al., 2001; Gupta al., 2014;
Krishnaswamy al., 2023), set cover (Gupta al., 2017: Abboud et al., 2019; Bhattacharya et al., 2019; Gupta & Levin, 2020; Bhattacharya et al., 2021; Assadi & Solomon, 2021), edge orientation (Brodal & Fagerberg, 1999; Sawlani & Wang, 2020; Bera et al., 2022), graph coloring (Solomon & Wein, 2020), maximal independent sets (Assadi et al., 2018), and spanners (Baswana al., 2012; Bhattacharya et al., 2022b).
Our rounding scheme for facility location in Section 3.2 can be seen as dynamic analog of the classic result of (Shmoys et al., 1997). Roughly, let R2 be the fractional service cost of a point/client j (we will define this carefully later). By Markov's ' inequality, for a constant 7 2 1, every client j must have a fractional mass of - 1/7 within the ball of distance 7 Rg from j. In (Shmoys et al., 1997) they show that greedily picking disjoint balls of this kind in order from smallest to largest radius and opening the cheapest facility within each is a constant approximate solution.
2. Preliminaries
In the classical clustering problems we study we are given a metric space (M, d) on n points. We assume without loss of generality that min,JeM dej = such that A = max dij is the aspect ratio of the metric space. In addition, there is set of points C C M we refer to as clients, and a set of candidate center locations F C M.* The algorithm outputs a solution which is a subset of the
Once again, as the underlying fractional solution changes over time, these service costs change, and we need to be careful with our online choices. As in the k-center case, our algorithm maintains set of "well separated"' balls of dif- ferent radii around certain points/clients and it also chooses cheap facility inside each such ball. If the total fraction inside a ball drops enough, we can charge our integral re-
'In k-ccentrr and k-median, we assume F M.
3

---

Competitively Consistent Clustering
candidate center locations, S S F. The constraints and objectives are different for each of the problems we study:
1.1 for the fully dynamic k-center problem is obtained by combining the guarantee the fractional solution along with the following theorem that we prove.
In k-center, the algorithm is allowed to open at most k centers and the goal is to minimize the maximal distance of client in C' to its closest open center.
Theorem 3.1 (Dynamic k-center rounding). Let x² be a fractional solution to the dynamic k-center problem that maintains solution that is B-approximation at any time, uses at most k' centers, and its total fractional recourse is R. Then, for any S 1/2, there is an algorithm that maintains an integral solution with at most (1 + 2e)k' centers that is (a: a)ppprxxiee at any time, and its total recourse is O (log(A)/e) R, where a = 3 2 5.28.
In facility location, the algorithm is allowed to open any number of centers (which we alternatively refer to as a facilities), but opening a facility in position E F incurs an opening cost of fi- The goal is to minimize the total opening cost plus the total service cost, defined as the sum of distances from the clients in C' to their nearest open facility.
The Algorithm: Our algorithm maintains at time set of open centers S For each i E St, let S t be the time in which the center is added to the solution and let = D min OPT } be the radius of the balls that can serve the clients when i was added to S (note that r; S A). With foresight, we set parameters a = =3- 2v2 and 8 = v2 and define B, == { dij S r and B := 6 di3 S a D*). We identify each facility with the ball around it, and count in our analysis the number of balls that we add or drop. Our algorithm is simple to describe and works as follows. At time we update the fractional solution and the value of OPT' (the radius of the k-center optimal fractional solution at time t). Then,
In k- k-median, the algorithm is allowed to open at most k centers and the goal is to minimize the sum of distances between clients and their closest center.
In the fully dynamic version of each of these problems, we are given at every time t = 1,...,T' T a different set of clients C² S .. The algorithm must maintain a solution St at each time step that is approximately optimal with respect to the clustering objective that time step, while also minimiz- ing the total recourse, defined as Ei= |S e St11|, More precisely, our goal in this work is to maintain an (ax (3)- approximate solution to the clustering objective while pay- ing recourse at most e. OPT REC where OPT REC denotes the optimal recourse of an offline solution that maintains a B- approximate solution at all times. For each problem, we use
REC
St St-1
Drop from St any i such that ΣjEB, 2² < -
OPT' denote the cost of the optimal fractional solution at time I.
Iteratively: as long as there exists client C* such that j & Ulest B (uncovered by our current solution).
3. A Algorithms
Add j to St (and B, is, as defined, of radius ry D³).
3.1. A rounding algorithm for fully-dynamic k-center
In this section we design a rounding algorithm for the fully dynamic k-center problem. Following Appendix 1, for every c C (0, 1] there is an algorithm that maintains a frac- tional solution 0 to the fully dynamic k-center problem satisfying the guarantees:
Drop from St any center/ball i E .S,i j such that
dy S Sr. + --.mmiffr (ri,(rs,r))
(3.1)
Analysis: We will prove by induction on the steps of the algorithm that the algorithm maintains the following invari- ants.
loy(2)
Σ
1:00
x' -'11
OPT
e
Σ
1 12
Vj (EETT
$EB9
(i) For each j E C², we have j E UiESt Bi
Σ
x (1+c))
Vt [
(ii) For all in, in E St: dig 2 ri, tri, 48-minnf min r In particular the balls around the centers are disjoint.
For an active client E C* and time t, By By= = (i M dy < min(3. (/B.. }}} is the set of centers at distance at most 3 OPT', and therefore feasibly serve client j at time t, and let D' min SanTB.OPT, A}. The bound in Theorem
(ii) For all e St. we have ΣjEB, 2 2 1 - E.
(iv) For all i E St, we have EjEB, 2 2
4

---

Competitively Consistent Clustering
In addition, we use the following potential function at time & E [7], with parameter 7) 1/logz(e (a - 8 - 1) = 1/ logz( (2 v2):
The invariants are clearly satisfied initially when there are clients, the fractional solution is and no centers were added. The following events may happen at time step t.
0² +++1 1) log A
00, 1
Σ 25}
1-11g to x². The fractional solution changes from x'-1
iES
jEB,
Facility such that EjEB, 2j < (1 c) is dropped in the first step.
log2
(3.2)
VES
A new center/ball around j is added, and then (pos- sibly) other centers/balls are dropped in the second iterative step.
Let N be the total number of balls dropped due to the first step of the algorithm until time t. Let N2 be the number of balls dropped until time t due to an addition of a new ball in the second (iterative) step of the algorithm. We prove inductively that,
The fractional solution changes: By our induction hy- pothesis and Invariant (ii) we have that for all i i2 E St de 2 Ti, + Tt, + 8 min(ra, Je Fey
) 1| - -x--=x'-11 x11111,, (3.3)
log A
and in particu- lar the balls are disjoint. The only term that depends on the fractional solution is (1+ log Al/e Eiesi max EjeB, 2}} in the potential function. Hence, Inequality (3.3) is maintained.
AN1 + +NN+ + A S So
where ANf, ANG and A'' is the change in the values of Ni. N2 and o' at time step t. In particular, we show that the RHS of the above equation as well as é are finite. Therefore, the number of balls that are dropped due to an addition of new ball at time step in the second iterative step, AN2, is finite and the algorithm terminates.
Facility such that Σje,, 2) < 1 1 is dropped: If this event happens, then AN = 1, AN; 0. and max EjeB, xx} 2 Thus, we have, ANí AN + A0' S (1 + 17 log2 A) + 1 logg
Before showing that the algorithm maintains these invari- ants, we show why these imply Theorem 3.1.
A S 0.
A new ball around j is added, and then (possibly) other balls are dropped: In order to analyze this event we need the following lemma, which we prove shortly.
Proof of Theorem 3.1. By Invariant (i) and the definition of B (recall, the radius of B is at most Dt < a. (e-B-OPT") the algorithm maintains at all times an (a -ppaprooxe solution. By Invariant (ii) the balls are disjoint, and by Invariant (ii) we have for all i e St that Σ 2} 2 1-c. Since the fractional solution satisfies Σ 1 < K' and S 1/2, the number of centers chosen by the algorithm is
Lemma 3.3. If j &f ULeS: Bi, and let r2 DD be the radius of the new added bull Bj. Then, there exists at most one i E St such that dig S T4 + rj + 0 min(rr.T:]) This ball (if exists) has radius Ti > (a 6 1) D'. After adding this new ball and possibly dropping at most one ball all invariants (ii), (iü), (iv) are maintained.
K' T- < (1 + 2e) K. Finally, by Inequality (3.3),
at most
(1 (log A/c)-R. it easy to verify that Φ0 0 and s² 2 -1 Eiesi log2 (9/r:) 2 -2k log A. As the number of additions of centers is at most the total number of drops of centers plus the final number of centers (which is bounded by k), the total recourse is bounded as claimed.
Ni + No
4- T" < 0
Given Lemma 3.3 we prove that the potential argument (Inequality (3.3)) is satisfied and the algorithm terminates. We observe that if indeed the main loop of the algorithm terminates after a finite number of steps, then by the main loop condition, Invariant (i) must be maintained.
Remark 3.2. Our analysis has an additional (constant) additive term that depends on the final number of centers. However, a more careful inspection of our proof shows that the number drops is bounded by O (log A/c) times the total decrease in the variables z/.- This fact along with the fact that the final number of centers plus 1) Etes: loga (A/r.) is bounded by O (log 5/c) times the total increase in the variables can be used to avoid this additive term in the analysis.
Since by the LP constraints we have for the new added ball Σ Bj 2j = E JEB, 2² 2 1, the term (1+7) Al/e. Eiss max (0, 1 - EjEB, z5} of the potential does not increases due to the addition of the new ball and possibly the drop of a single ball. Next, we have two cases.
A ball of radius r; is added and no ball is dropped. In this case AN, = 0 and the change in the LHS of Inequal- ity (3.3) is at most A < -1 logz that by invariants (iv) for the new added ball B, we have EieB, A/3 2 1. As by Invariant (ii) the balls are disjoint,
S 0. We note
Next, we consider different events that can happen at time one-by-one and prove that all the invariants are maintained.
5

---

Competitively Consistent Clustering
and Σ, 25 S (:1 + t), this step can occur most k[1 + +e) times.
fractional solution satisfying the guarantees
log( log(
|| - 11 5o
OPT
A ball of radius ry is added, and a single ball i with ry > (a - ò 1-11 1) ry is dropped. The LHS of Incquality
REC
Vij 2
VjEC', (T),
(3.3) increases by at most AN3 + A - 1 1og2
A
iEF
T3
1 log2 ( (+)- = 1 1-1-lon log2 I
Viy S x
Vj [T], 1I W [T]
S 1--- log (a- - 5 - 1) <
Σ Sect iEF
Σ
diouis S (1+ OPP
0, where the last inequality follows by the definition 7 = 1/ 1/log2(e) (a 8 1). As in each such step, the potential function decreases by at least 1, the potential function only decreases in the previous case, and | I O( log A), this step can also happen at most O log A) times. We conclude that the main loop of the algorithm must terminate after a finite number of steps.
SEF jEC
The variable of is the fraction to which facility at position E F is open at time t and vig is the fraction by which client j is served with facility i at time t. The bound in Theorem 1.1 for the fully dynamic facility location problem is obtained by combining the guarantee on the fractional solution along with the following theorem that we prove. and choosing == 1.
Proof of Lemma 3.3. Since client j is uncovered (i.e. j of Uses: Bi), we have d3 a D' for all i E St. The new added ball Bj is of radius ry D Thus, for any i E S such that di S ri try + min(r.,Ty] we have,
Theorem 3.4 (Dynamic facility location rounding). Let x! be fructional solution to the dynamic facilit location problem that maintains a solution that is 3-approximation at any time with total fractional recourse R. Then, there is an algorithm that maintains an interral solution that is (ax 3)-approximate at any time, and its total recourse is O (log A) R, where a 11.
T + (1 + 8)D* = + (1 +1+00 +0r;
2 r; rr 8 min ry) 2 dij > 0: D
Thus, for such ball must be that r; > (a
1) D
Assume for the sake of contradiction that there are two balls
Bi B,g such that diy S Ti +Ty + 8 min and d2gw I fig j + 8 (rin, rj}. Then
The Algorithm: any time t, for each j E C², let R3 EieF dijyi, be the fractional connection cost of client j. The algorithm maintains at any time a set of active clients A' and a set of open facilities St. For each client j e A there is (exactly) a single associated facility i, E St. Whenever the algorithm adds or removes a client from A it also adds/removes the associated facility from St. Let S t be the time a client (and the associated facility) were added to A' (correspondingly to St). We associate each j E A' with a radius ry and a ball B, = (i E F dej S Sry). With foresight, set the parameters a = 11, 5 = 2. = 10/9. 1/ (())))))))))) At time f, the fractional solution is updated from (a* ,. to (x v/"), and the algorithm is the following.
d,,,22 S Sdi.. + d
Sri, + +r, + 2r; + 8- min (ra: 13 + 8 min (ria, r
rí, +rs (2 26) r, = Pi, riz (2 + 28)- D
2 28
< <in + rip +
5 1 min mnin ri.)
The first inequality follows by the triangle inequality. The second inequality follows by our assumption. The next two steps follow by our above observation rj- D', and because Ti, > (a- - 8- - 1)- D' and Tt, > (a - -) -1)))D DD Finally, recalling our specific values of a = 3 + 2 and 5 = -2, we get that this last line is at most ri, tri, +6- min(fr, rtz }. which contradicts the inductive hypothesis that Invariant (ii) holds before adding ball By.
A' +- A <- St-1
Drop from A' (and correspondingly its associated fa- cility S*) any j E A' such that ΣieB, at < 1/a.
After adding the new ball of radius De and dropping at most one ball violating Invariant (ii), the new balls satisfy Invariant (ii). Finally, as j E C by the LP constraints Eyen, T = Eyen, 2 2 1 and therefore Invariant (iv)
Iteratively: as long as there exists j E Ct such that di > a R2 for all i E St.
E
holds.
Add the client to A', and set set 7 -. For client j add to St facility with minimal cost fo such that dij S STy.
3.2. A rounding algorithm for fully-dynamic facility location
Drop from A (and the corresponding facility in St) any i E A², + j such that dij S ri + ry + min(re.7y)
We turn to our dynamic rounding scheme for facility loca- tion. Following Appendix A.2, for every 6 E (0, 1] we have
6

---

Competitively Consistent Clustering
Analysis: We prove inductively on the steps of the algo- rithm that the algorithm maintains the following invariants:
Remark 3.5. Our analysis has an additional (constant) additive term that depends on the final fractional solution. However, more careful inspection of our proof shows that the number balls dropped is bounded by O (log A) times the total decrease in the variables x/,- This fact along with the fact that the final number of facilities plus Ollo A) Eier 2, is bounded by O (log A) times the total increase in the variables z can be used avoid this additive term in the analysis.
(i) Each j E C², minkes dij S a Ry
(ii For all J1,32 E A:: din 2 T + T
12 + 8
min(ra.- In particular the balls around the clients in A' are disjoint.
(iii) For all j E A', we have Eien, 5 2 1/4- 1/11.
(iv) For all j E A", we have EieB, x M 1/7 = 1/10.
Next, we consider different events that can happen at time step one-by-one and prove that all the invariants are main- tained. The invariants are clearly satisfied initially when there are no clients, the fractional solution is O, and no facilities were added. The following events may happen.
In addition, we use the following potential function time t e [T].
(1 + 17 log (A))
The fractional solution changes.
Φ'_
Σ i
max
0,1
1
fjj
Client j such that Σien, xt < 1/a is dropped.
7
B.
A new ball around client j is added, and then (possibly) other clients/balls are dropped.
" log2
EEA
(3.4) Let N be the total number of balls dropped due to the first step of the algorithm until time I. Let Nţ be the number of balls dropped due to an addition of new ball in the second (iterative) step of the algorithm. We prove inductively that,
The fractional solution changes: By our induction and Invariant (ii) we have that for all i,, ig S di Z na +Ti +8-min(ra: T'ta J. and in particular the balls are dis- joint. Only the term (1 - 1/7 - 1/a) .(1+ 7)- log)(
ΣiEA' max fo, (7 1)/7 ExEB, 2)} depends on the fractional solution and Inequality (3.5) is maintained.
AN1 + AN2 + A <O (log || --'-'11' I1a (3.5)
where AN ANG and 4 is the change in the values of
Client i (and its corresponding facility) such that ΣjEB, 2} < 1 is dropped: If this event happens, then AN 1, 1,NN; O, and max 1 - 1/7 EjEB, #1} 2 1- 1/7 1/a. Thus, we have,
Ni, N2 and r' at time step f. In particular, we show that the RHS of the above equation as well as 6 are finite. Therefore, the number of balls that are dropped due to an addition of new ball time step in the second iterative step, ANg, is finite and the algorithm terminates. We show first that these invariants imply Theorem 3.4.
AN + AN + Agt
< 1 - 1/7 1/a
A r
(1 + +1 logg( + loga
Proof of Theorem 3.4. By Invariant (i), the total service cost is at most a Ejece RiJ.
1/7 - 1/a
50.
Since ig. the facility associated with client j E AS, is of minimal cost in Bj, we have fi, I EiEB, ft r (EiEB, x S a Eveb, ft x/. where the final in- equality is by Invariant (iii) that we maintain for all j E A Lien, x! 2 1/o. By Invariant (ii) the balls B, are dis- joint, and hence the total cost of opening facilities is at most a EeEF fart. Therefore, our solution is an (a 0..9. 3)- approximation.
A new ball around j added, and then (possibly) other balls are dropped: In order to analyze this event we need the following lemma, which we prove shortly.
Lemma 3.6. Suppose the algorithm adds a client j such that di > a- Rt, for all E St. and let T; = - R3 be the radius of the new added ball B, around j. Then, there exists at most one client i E A' such that daj S r; + r3 + 5 minfr.; rz and if such client exists then r; > 21/1 .r After adding this new client/ball and possibly dropping at most one client/ball all invariants (ūi), (iä), (iv) are maintained.
Finally, by Inequality (3.5) Nf + N + Φ' Φ <
O (log EL || x ||. It easy to verify that
T0 = 0 and g' 2 - (1-1/7 1/4) (1+ log,(A))
EIEA' E,eB, xf 2 -C'log A Eie zf. where C' is some constant, Thus, the total recourse is bounded.
Given Lemma 3.6, we only need to prove that the po- tential argument (Inequality (3.5)) is satisfied. Since by
LI
7

---

Competitively Consistent Clustering
the LP constraints and markov inequality we have for the new added ball EieB, of LieB, x/ 2 1 1/7, then the term (1 - 1/1 1/a) (1 + 7) 10 (A)) EiEr' max { (7. 11/7 - EjEB, 25 -1j//-/EBBB,..
3.3. A rounding algorithm for fully dynamic k-median
With the setup from previous sections, our algorithm for k- k-median is very simple to deseribe and to analyze. Given fractional solution for the problem formulation in Ap- pendix A.3, we run the rounding algorithm from Section 3.2, with facility costs Si = 0 for all i E M. The bound in Theo- rem 1.1 for the fully dynamic k-median problem is obtained by combining the guarantee on the fractional solution along with the following theorem that we prove.
of the potential
does not increases due to the addition of the new ball and possibly the drop of a single ball. Next, we have two cases.
A ball of radius ry is added and no ball is dropped. In this case AN2 = 0 and the change in the LHS of Inequality (3.5) is at most A& S -1) log, (A/r,) S O.
Theorem 3.7 (Dynamic k-median rounding). Let x' be a fractional solution to the dynamic k-median problem that maintains solution that is B-approximation at any time, uses at most k' centers, and its total fractional recourse is R. Then there is an algorithm that maintains an integral solution with at mosl a-kk' centers that is (a-33- -approxxieeee at any time, and its total recourse is O (log (A)) R, where a 11.
A ball of radius ry is added a single ball with r; > 2//n.ry is dropped. The LHS of Inequality (3.5) increases by at most AN2+ + I 1 1-17log2 +7- (A/r.)= = 1 1- logg (r/rr) S 1- - 1) logg (21/1)= S 0.
Proof of Lemma 3.6. For the client j. we have di > a. R for all E St. The new added ball B, is of radius r, = 7-
Let E A be any client such that daj S r; + r3 + 8. min(rs, ry]; and let i' be the associated facility of i. We have 2r, 22,++00 (1+ (1+)rr 2 r; trttr + ri), 2 die dij 2 dvj > a R2j = Gry. where the second inequality follows by the guarantee that facility i' is at distance at most r; from client i, and the guarantee on dej. The third Inequality is by the triangle inequality. The last inequality holds because j > Rj.
Proof. The approximation and recourse guarantees are im- mediate from Theorem 3.4, and it remains to show that the algorithm never holds more than O(k)) centers.
Inspecting the proof of Theorem 3.4, by Invariant (ii) the balls B, are disjoint, and by Invariant (iii) we have for all E F' that ΣJEB. =/ 2 1/a. Since the fractional solution satisfies Σ o < k', the number of centers chosen by the algorithm is at most a a.K.
Thus, for such a ball it must be that r. > (2 = Next,
21/7 ry (recall that 7 = 1/ (o(((==(++)))22))) assume to the contrary that there are two balls B,, Big such that diy S Tiy + r3 + 8- min(rig: T3} and dizd S Ti +ry
4. Experiments
+ min(fia. Jy}- Then
We evaluate our three clustering algorithms experimentally UCI Machine Learning repository datasets: Glass Identi- fication (German, 1987), Wine Quality (Cortez et al., 2009), and Airfoil Self-Noise (Brooks et al., 2014). Due to space considerations, we defer details of our experimental setup and the plots of our experiments to Appendix D. We ob- serve that our algorithm indeed maintains an objective value within the predicted bound, and in fact significantly out- performs the worst-case bound predicted by the theorem. In the case of facility location and k-median, our objective value is almost the same as the best possible objective value. On all of our data sets, our algorithm's 's recourse seemss to be < T, and even seems bounded by a constant in many cases. This justifies our focus on competitive recourse, as opposed to absolute recourse. Interestingly, in many cases (especially for k-center), our online algorithm's 's recourse is lower than the offline fractional optimum recourse. Note that this is possible because our algorithms is using resource augmentation, while the fractional optimum is not. Finally, we observe that in our experiments for both k-center and k-median, even though our algorithm is allowed to open (1 + c) centers, they tend to use no more than & centers.
di,,5 S d + diz.j
$ ri, +ri + 2r, + 8- minfra, r5} + 8- min(rin:))) my)
Sra,
< Th +r/s + +(2+ + 28) .r
4 + 46
< T/ + + 0/7 (1 + 8)
min(rr.,Taal
The first inequality follows by the triangle inequality. The second inequality follows by assumption. The third and fourth inequality follow by our above observation that Ts, > 21/y .ry and riz= > 21/1 .Ty- Finally, this is strictly less than ri, +r,, + min(ri,, } by our specific setting of the parameters. This contradicts the induction hypothesis that Invariant (ii) held before ball B, was added.
After adding the new ball of radius rj. and dropping at most one ball that violates Invariant (ii), the new balls satisfy Invariant (ii). Finally, because j E A' by the LP constraints, by Markov's 's Inequality (since ry 7 R²))
EiEB, 2 = EiEB, 2/ 2 1 - 1/7 and therefore Invariant (iv) is maintained.
8

---

Competitively Consistent Clustering
5. Conclusion
Discrete Algorithms, SODA 2012, pp. 1681-1689, 2012. cited on page 3
In this work we initiate the study of consistent clustering with competitive recourse guarantees. We show how to maintain 0(8) approximations for k-center, facility loca- tion and k-median with (log [F] log A) OPTREC recourse (using (Ik) centers for k-center and k-median), and showed that any such algorithm must incur recourse of least ((min (log FI,, log {}} OPT 3
Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., and Naor, J. The online set cover problem. SIAM Comput, 3912):61-13377) 2009. - cited on page 3
Arya, V., Garg. N., Khandekar, R., Meyerson, A., Munagala, K., and Pandit, V. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):5444500 2004, + cited on page 3
There are plenty of natural open questions. The most ob- vious is to close the gap between upper and lower bounds. Another interesting question is to understand whether using (1 + 6). k centers (or (kk) centers) is necessary, or whether one can do with exactly centers. A weaker interim goal to give an algorithm for k-median which only opens (1 () k centers, without suffering I/e factor in the ap- proximation. We note even offline rounding algorithms for k-median are fairly involved (Charikar et al., 2002), and his- torically came after simpler bicriteria rounding algorithms (Lin & Vitter, 1992). It would also be beneficial to better understand the relationship between algorithms with abso- lute resource guarantees and algorithms with competitive recourse guarantees. It would be interesting to benchmark our algorithms on real world datasets, and in particular to evaluate how they compare to existing algorithms with abso- lute recourse guarantees. Finally, it would be interesting to explore competitive recourse algorithms for other clustering objectives in the fully dynamic model.
Assadi, S. and Solomon, S. Fully dynamic set cover via hypergraph maximal matching: An optimal approximation through local approach. In Mutzel, P., Pagh, R., and Herman, G. (eds.), 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference). volume 204 of LIPIcs. pp. 8:1-8:18. Schloss Dagstuhl- Leibniz- Zentrum für Informatik, 2021. cited on page? 3
Assadi, S.. Onak, K. Schieber, B., and Solomon, S. Fully dy- namic maximal independent set with sublinear update time. In Proceedings of the 50th Annual ACM SIGACT Symposium on theory of computing, pp. 815-826, 2018. + cited on page 3
Awasthi, P., Blum, A., and Sheffet, O. Center-based clustering under perturbation stability. Inf. Process. Lett., 112(1-2):49 2012. - cited on page 2
Awerbuch, B., Azar, Y., Plotkin, S. A., and Waarts, O. Competitive routing of virtual circuits with unknown duration. J. Comput. Syst. Sci., 62(3):385- -97, 2001. - cited on page 3
Bansal, N., Buchbinder, N., Madry, A., and Naor, A solylogarthmic-copplee algorithm for the k-server problem. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 201 pp. 267-276, 2011. - cited page
Disclosure of Funding
The work of Niv Buchbinder is supported in part by the Israel Science Foundation (ISF) grant no. 3001/24, and the United States Israel Binational Science Foundation (BSF) grant no. 2022418.
Bansal, N., Buchbinder, N., and Naor, J. A primal-dum dual randomized algorithm for weighted paging. ACM, 59(4):19: 19:24, 2012. + cited on page
Baswana, S., Khurana, S., and Sarkar, S. Fully dynamic ran- domized algorithms for graph spanners. ACM Transactions on Algorithmms (TAI.G), 8(4):1-51, 2012. - cited on page 3
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bera, S. K., Bhattacharya, S., Choudhari, J., and Ghosh, P. A new dynamic algorithm for densest subhypergraphs. Proceedings of the ACM Web Conference 2022, pp. 1093-1103, 2022. + cited on page 3
References
Bhattacharya, S., Henzinger, M., and Nanongkai, D. A new de- terministic algorithm for dynamic set cover. In Zuckerman, D. Foundations of Com-
Abboud, A., Addanki, R., Grandoni, F., Panigrahi, D., and Saha, B. Dynamic cover: improved algorithus and lower bounds. In Charikar, M. and Cohen, E. (eds.). Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pp. 114 125. ACM, 2019. cited page
(cd.), 60th IEEE Annual Symposium puter Science, FOCS 2019, Baltimore, Maryland, USA, Novem- ber 9-12, 2019, pp. 406-423. IEEE Computer Society, 2019. -> cited on page 3
Bhattacharya, S., Henzinger, M., Nanongkai, D., and Wu, X. Dy- namic set cover: Improved amortized and worst-case update time. In Marx, D. (ed.), Proceedings of the 2021 ACM-SIAM Symposium Discrete Algorithms, SODA 2021, Virtual Con- ference, January 10 13, 2021, pp. 2537-2549. SIAM, 2021. cited on page
Adamaszek, A., Czumaj, A., Englert, M., and Räcke, H. An Ollo k)-competitive algorithm for generalized caching. In Proceed- ings of the Twenty-Thin Third Annual ACM-SIAM Symposium on

---

Competitively Consistent Clustering
Bhattacharya, S., Lattanzi, S., and Parotsidis, N. Efficient and sta- ble fully dynamic facility location. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems 35: Annual Confer- ence on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022a. + cited on page 1
Cohen-Addad, V., Lattanzi, S., Maggiori, A., and Parotsidis, N.
Online and consistent correlation clustering. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári C., Niu, G., and Sabato, S. (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 4157-4179. PMLR, 2022. + cited on page
Bhattacharya, S., Saranurak, T., and Sukprasert, Simple dy- namic spanners with near-optimal recourse against an adaptive adversary. In 30th Annual European Symposium on Algorithms (ESA), volume 244 of LIPlcs, pp. 17:1-17:19, 2022b. - cited on page 3
Cortez, P., Cerdeira, A., Almeida, F., Matos, T., and Reis, J. Wine Quality, UCI Machine Learning Repository, 2009. DOI: http:://dii.org/1...o 0tgg//0...44///5555TT + cited on page 8
Fichtenberger, H., Lattanzi, S., Norouzi-Farte A., and Svensson, O. Consistent k-clustering for general metrics. In Marx, D. (ed.), Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms,, SODA 2021, I, Virtual Conference, January 10 13, 2021. pp. 2660 2678. SIAM, 2021. ~> cited on page 1,2
Bhattacharya, S., Buchbinder, N., Levin, R., and Saranurak, T. Chasing positive bodies. In 64th IEEF Annual Symposium on Foundations of Computer Science, FOCS 2023, pp. 1694-1714. IEEE, 2023. - cited on page 2, 11
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 Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, II, USA, October 27-30, 2024, pp. 216-227. IEEE, 2024a. - cited on page 1
Forster, S. and Skarlatos. A. Dynamic consistent k-center clus- tering with optimal recourse. Azar. and Panigrahi, D. (eds.). Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pp. 212-254, SIAM, 2025. + cited on page
Bhattacharya, S., Costa, M., Lattanzi, S., and Parotsidis, N. Fully dynamic k-center clustering made simple. CoRR, 0bs/24100.11700 2024b. + cited on page I
Fotakis, D. On the competitive ratio for online facility location. Algorithmica, 50(1):1-57, 2008. -> cited on page 13
Brodal, G. S. and Fagerberg. R. Dynamic representations of sparse graphs. In Algorithms and Data Structures: 6th International
German, B. Glass Identification. UCI Machine Learning Reposi- tory, 1987. DOI: https://bbi.orgg/.222333///v// on page
cited
Workshop, WADS Vancouver, Canada, August 11-14, 1999 Proceedings 6, pp. 342-351. Spriner,, 1999. + cited on page 3
Gonzalez. T. F. Clustering minimize the maximum intercluster distance. Theor. Comput. Sci., 38:293-3066 1985. + cited on page 3
Brooks, T., Pope, D., and Marcolini, M. Airfoil Self- Noise. UCI Machine Learning Repository, 2014. DOI: https://doi.or/// 00/9////.0043////3332 + cited on page 8
Byrka, J. and Aardal, K. I. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput., 2966):2212-2211 2010. cited page
Gu, A., Gupta, A., and Kumar, A. The power of deferral: Maintain- ing a constant-comp competitive Steiner tree online. SIAM J. Comput., 45(1):1-28, 2016. -> cited on page
Byrka, J.. Pensyl. T. W., Rybicki, B., Srinivasan, A., and Trinh, K. An improved approximation for k-median and positive correla- tion in budgeted optimization. ACM Trans. Algorithms, 13(2):
Guha, S. and Khuller, Greedy strikes back: Improved facility location algorithms. J. Algorithms, 31(1):228-244 1999. + cited on page 1
13:1-23:31, 2017. + cited on page
Guo, X., Kulkarni, J., Li, S., and Xian, J. On the facility location problem in online and dynamic models. In Byrka, J. and Meka. R. (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of LiPlcs, pp. 42:1-42:22 1-2:23... Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2020. + cited on page 1
Chan, T. H., Lattanzi. S., Sozio, M., and Wang, B. Fully dynamic k-center clustering with outliers. Algorithmica, 86(1):171-193 2024. + cited on page 1
Charikar, M. and Guha, S. Improved combinatorial algorithms for facility location problems. SIAM J. Comput., 3444):803-824, 2005. - cited on page
Charikar, M., Guha, S., Tardos, É., and Shmoys, D. B. A constant- factor approximation algorithm for the k-median problem. J. Comput. Syst. Sci., 65(1 12291999, 2002. + cited on page 9
Guo, X., Kulkarni, J., Li, S., and Xian, J. Consistent k-median: Simpler, better and robust. In Banerjee, A. and Fukumizu, K. (eds.), The 24th International Conference on Artificial Intelli- gence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Re- search, pp. 1135 1--11126 1143, PMLR, 2021. + cited on page
Cohen V. Hjuler, N. Parotsidis, N., Saulpic, D., and Schwiegelshohn, C. Fully dynamic consistent facility location. In Wallach, M., Larochelle, H., Beygelzimer, A., d' Alché- Buc, F. Fox, E. B., and Garnett, R. (cds.), 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. + cited on page!
Gupta, A. and Kumar, A. Online Steiner tree with deletions. In Chekuri, C. (ed.). Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 201 4, pp. 2p.4555-66.. SIAM, 2014. + cited on page 3
10

---

Competitively Consistent Clustering
Gupta, A. and Levin, R. Fully-dynamic submodular cover with bounded recourse. In Irani, S. (cd.), s IEEE Annual Sym- posium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pp. 1147-1157. IEEE, 2020. + cited page
Moseley, B., Newman, H., and Pruhs, K. Online k-median with consistent clusters. CoRR, 2atp/2333.15379, 2023. + cited on
page 1
Sawlani, S. and Wang, J. Near-optimal fully dynamic densest subgraph. In Proceedings of the 52nd Anmual ACM SIGACT Symposium on Theory of Computing, pp. 181-193, 2020. + cited on page
Gupta, A., Kumar, A.. and Stein, C. Maintaining assignments online: Matching. scheduling. and flows. In Proceedings of the Twenty-Fifte Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 468 (68-479. SIAM, 2014, + cited on page 3
Shmoys, D. B., Tardos, É., and Aardal, K. Approximation algorithms for facility location problems (extended abstract). In Leighton, F. T. and Shor, P. W. (eds),, Proceedings of the Twenty- Ninth Annual ACM Symposium on the Theory of Computing, EI Paso, Texas, USA, May 4-6, 1997. pp. 265 274. ACM, 1997. - cited on page 3
Gupta, A., Krishnaswamy, R... Kumar, A., and Panigrahi. D. Online and dynamic algorithms for set cover. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2017, Montreal, QC, Canada, June 19-23, 2017. pp. 537- 550. ACM, 2017. + cited on page 3
Solomon, S. and Wein, N. Improved dynamic graph coloring. ACM Transactions on Algorithmss (TALG), 16(3):1-24 2020. + cited on page
Hochbaum, D. S. and Shmoys, D. B. A unified approach to approximation algorithms for bottleneck problems. J. ACM, 33(3):533 550, 1986. + cited page
Williamson, P. and Shmoys, D. The Design of Approximation
Algorithms. Cambridge University Press, 2011, ISBN 978-0- 521-19527-0. + cited on page 3
Imase, M. and Waxman, B. M. Dynamic Steiner tree problem. SIAM Discret. Math, 4(3):69-338 384, 1991. + cited on page
Jain, K., Mahdian, M., and Saberi, A. A new greedy approach for
facility location problems. Reif, H. (ed.), Proceedings on
A. Formulations as positive body chasing
34th Annual ACM Symposium on Theory of Computing, May
19-21, 2002, Montréal, Québec, Canada, pp. 731 ACM, 2002. + cited on page
The fractional versions of our clustering problems is cap- tured by a framework referred to as Positive Body Chasing suggested recently in (Bhattacharya et al., 2023). In the chasing positive bodies problem, we are given a sequence of bodies K, = (x² E RT C'aa 2 1, ptx S 1} revealed online, where C* and Pd are matrices with non-negative entries. The goal is to (approximately) maintain a point z' E K₁ such that the total mo-oovemnt, Σ, || -- I|1, is minimized where x² = O. More generally, given weight w E R", we want to minimize the weighted m--movement, Σ, w. Ei movement as fractional recourse. In (Bhattacharya et al., 2023), the authors designed an online algorithm for this problem proving the following theorem.
Jain, K., Mahdian, M., Markakis, E., Saberi, A., and Vazirani, V. V. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM, 50(6)4795-824 2003. >> cited on page
Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., and Wu, A. Y. A local search approximation algorithm for k-means clustering. Comput. Geom., 28(2-3): 89-112, 2004. -> cited on page 3
We sometimes refer to this &
Krishnaswamy, R.,, Li, S., and Suriyanarayana, V. Online unrelated- machine load balancing and generalized flow with recourse. In STOC, 2023.- + cited on page 3
Eqcki, J., Oéwieja, J., Pilipezuk. M., Sankowski, P., and Zych, A. The power of dynamic distance oracles: Efficient dynamic algorithms for the Steiner tree. In Proceedings of the forty- seventh annual ACM symposium Theory of computing, pp. 11-20, 2015. + cited on 3
Theorem A.1 ((Bhattacharya et al., 2023)). For any E (0, 11. there is an O (1/e log ccompeicoeeeiiiive algorithm for chasing positive bodies in E, such that xt E K2t {a² E &R, C² 1, 1' $1+E) E) at time t, and d is the maximal number of non-negative coefficients in cover- ing constraint.
Eacki, J., Hacupler, B., Grunau, C., Jayaram, R., and Rozhoñ, V. Fully dynamic consistent k-center clustering. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA), pp. 3484-3484. SIAM, 2024. -> cited on page 1,2
We next list the dynamic clustering problems that we study, formulate each problem in the framework of Theorem A. and derive the guarantees on the fractional solution that is produced in an online fashion.
Lattanzi, S. and Vassilvitskii, S. Consistent k-clustering. In Precup. D. and Tch, Y. W. (eds.), Proceedings of the 34th International Conference on Machine Learning, ICMI. 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Ma- chine Learning Research, pp. 1984. PMLR, 2017. cited page
A.I. Fractional dynamic k-center
Let af be an indicator for the opening of center at posi- tion i E M at time t. For each j E C' let B = {i E M ddy I min OPTT A}} be the set of points that are within distance at most 3 'OPT' from client j. The set B
Lin, J. and Vitter, J. S. Approximation algorithms for geometric median problems. Inf. Process, Lett., 44(5):245-249, 1992. - cited on page 9

---

Competitively Consistent Clustering
is the of points that can serve the client at time in 3-approximate solution. Given these variables, the follow- ing is formulation of the offline fully dynamic k-center problem.
is at most the optimal solution the original formulation, and can transform the resulting fractional solution online to solution to the original LP at no additional cost. Note also that we do not pay recourse for changing the variables Vij. This is captured by giving these variables weight zero in the weighted & -noor of the positive body chasing problem. Let x", x',y" y be the optimal fractional solution, and let OPT
Eieny of 2 1, Vj E C², , [T]
T min)
1/1
Em= k
Hence, by Theorem A. we get the following guarantee. For any E (0, 1], there is an online algorithm that produces a fractional solution (x, y) 2 0 to the fully dynamic facility location problem such that,
E 1(=1 -|=111=---- x
E [T]
o 200 O, M, [T]
Let be the optimal fractional solution, and let OPT REC Ei= || 2 As the set of constraints at time covering/packing formulation, the fractional fully dy- namic k-center problem captured by the positive body chasing problem. Hence, by Theorem A.1 we get the fol- lowing guarantec. For any (0, 1]. there is an online algorithm that produces fractional solution x 2 0 to the fully dynamic k-center problem such that,
Log((F1/e)
Σ 1| -
11
50
OPT
Σ
Vij 21
EEF
Vig
S 2
Vie eie t [T],
Fiat
Σ
dijuy S (1+c)- 8 OPT
x x--1 -0
( log(n/c))
OPTRR REC!
REF
KEF,EC
Vt E [T7.
6
21
Vj (j,
A.3. Fractional k-median
Σ
o (1+ 1=
Vt E
Let æt be an indicator for the opening of a center at position E M at time (. Let v/g be an indicator for serving client j with center at time t. Given these variables, the follow- ing is formulation of the offline fully dynamic k-median problem.
A.2. Fractional facility location
ar be an indicator for the opening of a facility at position i F at time f. Let yi be an indicator for serving client j with facility& i at time L. Given these variables, the following is a formulation of the offline fully dynamic facility location problem.
Σ vis 2 1, iEM
Σ U/j 1, SEF
Vj E [
v Stt
VjE C [T]
S/
T
T
Vjj Vj CE
min
1
x² 1111
Σ 4 k.
min
|
x 1|2
Σ Ehat +
Σ dishis
REM
1=1
Vt [T]
iCF
iEF,jCC
Σ do & B OPT",
8 OPT", [T a d, 20,
REM JEC
ViE t
v [T]
Although the above formulation is not a novering-packing LP due to the constraint vřz S æ4; we show in Appendix B that it is possible to work with an equivalent formulation that is a eiveringppacking This means that the fractional fully dynamic facility location problem is captured by the positive body chasing problem. In particular, we compete with an optimal solution to the modified formulation which
As in the case of facility location, we can transform this into a covering-packing formulation (See Appendix B). Once again by Theorem A. for any e E (0, 1]. there is an online algorithm that produces fractional solution (s, y) 2 0 to
12

---

Competitively Consistent Clustering
the fully k-median problem such that:
A solution to the modified formulation can be trans- formed online into a feasible solution to the original formulation with the same recourse.
[o0(())
Σ | x1-2
50000 =0
OPT REC
Σ Viz 21
VjEC (T],
Proof. Let (æ, y) be solution to the original formulation. We need to prove that it satisfies all the new constraints of the form (B.1). This is true since.
Mig I x
Vi M,M, [ C E (T].
(1
44 [7],
Σ
Σ SEF\
J/ iEF
2 1,
Σ
desii'g < (1
14 [T].
REF
N JEC
where the first inequality holds since vij < x and the second inequality holds by the original constraint that ΣieF Vij - 1.
B. A covering-packine LP formulation for the facility location and the k-median Problems
On the other direction, if (xr, y) is a solution the modified LP, then setting vij min (uly. mt} satisfies the constraint
We show here that the facility location problem can be captured by a povering-packing formulation. The arguments for the k- k-median problem are similar.
viy S xt. Next, if EieF means that for F' = {i E
iEF Mij
REF min = < it
F
2 2
Wiyh
Recall, the formulation in Section A.2. Let arf be an indi- cator for the opening of facility at position i E F at time t. Let vij be an indicator for serving client j with facility i at time I. Let OPT be the optimal facilitiy location ob- jective at time t. Given these variables, the following is a formulation of the offline fully dynamic facility location problem.
Σ Mly + Σ iEF
of
Σ
min #/} < 1.
SEP(F
REF
This contradicts the feasibility of the solution 2; y to the modified LP. Hence, the solution z/} is feasible to the origi- nal LP. Moreover, since we didn't 't modify the variable at, has the same recourse.
Finally, given solution x; y to the modified LP check- ing for each client j, whether the constraint with F' {i of 2 v'y satisfies Eigri Vis + Eigr ot Eier min a/} > 1 suffices for the feasibility of the LP, and otherwise we get violated constraint.
Σ
vig 21
CjEC (T],
SEF
Vj VjEC (T),
C. Lower bounds
Σ fiat +
Σ
drpiyy 3 OPT
te [T].
In this section we prove the following lower bounds for any randomized dynamic clustering algorithm. We draw ideas from (Fotakis, 2008).
KEF
iEF,jCC
2/1 v/j 20 0
[T]
Theorem 1.2 (Lower Bound). Suppose there is random- ized algorithm that given a parameter B > 1 as an input maintains (a. apprroximmatoon for one of fully-dynamic facility location, k-center, or k-median. Then this algorithm has recourse at least Mmin [F), log, A}. A}-OPT Rec- For k-center and k-median, the lower bound holds even if the algorithm allowed to open O(k) facilities.
The above formulation is not a covering covering-packing formula- tion. However, is not hard to transform it into a covering packing formulation by removing the constraint vl S at and introducing in addition to the constraint Eier Viy 2 1, the following exponential number of constraints:
Σ Biy +
Σ 11 F
[T.
(B.1)
Proof. The lower bounds share common ideas, but the ex- act metric, the adversarial sequence, and the cost analysis are different for each clustering problem. Therefore, prove the lower bounds separately for each problem. For all these problems, we prove lower bound for an online fractional solution that may generate a fractional solution to the linear formulation. Since the marginal probabilities of any randomized algorithm induce fractional solution with
We observe the following. Lemma B.I. The formulation is separable in poly- nomial time. Moreover,
Any solution to the original LP is feasible to the new formulation.
13

---

Competitively Consistent Clustering
the k-center objective for every time / in the phase simultane- ousty. The cost of this solution at any round & 0,.... h is
Level h
(4c)
Level h
h-1-t Σ
OPT' =
(40)* 2 -2((4))--11
Level 2
At time = h, we have OPT = 0. The recourse of this solution is per phase.
4c
Level 1
On the other hand, we also observe that if at time L 1,..., h the algorithm has =t, + x'R S 1/2, then the algorithm's 's solution has cost least e. OPT', To see this, note that the two clients at 11 and " must be matched fractionally to extent at least 1/2 to a center outside the subtree rooted at r", The distance to this center is at least twice the cost of the edge between r' and its parent ,d1 which is at least
Level 0
Pigure! Illustration of the HST-metric H.
at most the same cost, such a bound immediately translates bound on any randomized algorithm.
We will reuse the same base metric for our bounds. Let H be a uniform binary (4c)-HST with n leaves and height h = logg n. The leaves of the tree are at level 0, and the root of the tree, r, is at level h. The edges that connect a node at level i - 1 to a node at level i (for = I,.... 1) have cost (4c)(=1 For a non-leaf node w, let wa and wz be the right and left child of respectively.
1/ 2.
2 .2 (4c) > 2 c-
Therefore, any algorithm maintaining an approximation better than with respect to OPT' must have at each time = I....,h - 1 at least a 1/2 fraction of center open in the subtree of r" Since the algorithm can open at most one center at any given time, and by construction of the adversarial sequence, at every time f = 0,... h - 1, the algorithm has more fractional mass in the child of r that is not r+1, the algorithm must open at least 1/4 of a center to maintain a c-approximation. Hence the algorithm must open total of (2(h) centers over the course of the phase, where we observe that size of the metric is n 2 and the aspect ratio is A = O((4c)))
A lower bound for the (ully-Dynamic k-center problem. Assume that there exist fractional algorithm that main- tains at all times at most k centers with an approximation ratio strictly less than e with respect to the optimal solu- tion at time / (we later extend this bound to a scenario in which the algorithm is allowed to pen b & facilitics). We prove that such an algorithm has recourse competitiveness M(min n, log, A ), and our bounds hold even when 1. Once again we reuse the (4c)-HST H defined above. This time, the metric space, as well as the possible locations for the clients and facilities is defined only by the n leaves of the tree and the distances induced by the binary HST.
Mt. This sequence may be repeated.
Finally, suppose that the algorithm is allowed to maintain total mass of b. = facilities at each time step. Then, at the beginning of each phase, there exists a subtree of height h' 2i(h- log, b) with total initial mass of at most 1/4 (the subtree with minimal mass among the 4b disjoint subtrees of height h - (4b).. The adversary can restrict its sequence to this subtree and the algorithm, again, must open 1/4 of a facility in each level of the tree, paying a total opening cost of 1(0 b) during the phase. Overall, the lower bound on the recourse competitiveness Qmmin n, log, A b).
The adversarial sequence again happens in phases, and each phase is divided into h time steps. At time 0, initialize the node ,0 to be r, the global root of the metric H. For every time t = 0, 0,..., h, the adversary creates two clients at u² and u'z. where these are the leftmost and rightmost leaves descendant of r' respectively. The adversary then removes any clients requested in the last time step. Let æ1 and o'n be the total fraction of facilities that the algorithm opens in the subtrees of rž and r'k (the two children of the node r¹). If at, 2 2²R then set the node +++ == r otherwise set r+1 r1- Finally, iteration t = h there is single client located at single leaf v. After time h, the adversary removes all clients, and we may repeat this phase/sequence starting from the root.
A lower bound for the dylamcd facility location problem. Assume that there exists a fractional algorithm that maintains at all times an approximation ratio strictly less than with respect to the optimal solution at time t. We prove that such an algorithm has recourse competitiveness Ω (mmin (log FF), log, A}.
The underlying metric is the (4c)-HST H defined above. The set of possible facility locations, F, is the set of n leaves of the tree, but we allow clients to arrive at any internal node.
We observe that in every phase, opening a center on the last node of the sequence gives the lowest possible value for
14

---

Competitively Consistent Clustering
Finally, the cost of opening a facility is f (4c)--1 (in other words, the cost is uniform).
therefore the algorithm also must remove all its facilities. Hence, we may repeat the phase/sequence again by initiating new client at the root.
The request sequence is in phases, each of which is divided into h time steps. At time 0 there is single client located at the root. Henceforth, for all time = 1,..., h let u² be the node at which clients appeared at time & 1, and let oi and z'x be the fractional mass of facilities that the algorithm allocates in the subtrees of u and uh respectively. If af 2 2'R then the adversary generates (4c)* clients at u' if x' < ' then the adversary generates (4c)² clients at "i instead. The adversary then removes any client requests at u². Eventually, at time h, a set of (4c)* clients arrive at some leaf v. After time h, all clients leave, and we may repeat this phase/sequence starting from the root.
A lower bound for the fully-dynamic k-median prob- lem. Assume that there exist fractional algorithm that maintains at all times at most &o centers with an approxi- mation ratio strictly less than e with respect to the optimal solution at time (we later extend this bound to a scenario in which the algorithm is allowed to open b A facilities). We prove that such an algorithm has recourse competitive- ness {min ( flog n, log, 4}) with respect to an algorithm that may maintain 2-approximate solution. That is, the algorithm is paying (m (log n, log, A}) OPT Our bounds again hold even when k = 1.
Note that in every phase, opening a single facility on the last leaf e of the sequence gives the lowest possible value for the facility location objective at every time ć in this phase. This strategy uses total recourse of per phase (opening a single facility at the beginning of the phase and closing it at the end of the phase). The cost of this solution at any round t == O....,h - is:
The metric space and the client sequence are identical to those in the kicenter instance above. This time, we observe that in each phase, opening a single center on the final v of the sequence is at most 2-approximation with respect to OPT' for all time steps in the phase simultaneously. (For every t, the optimal solution is to open a center on one of ut or w(x)) The cost of this solution at any round = O.....h h - 1 is
h-t-1
OPT' = =f (Ac)*
Σ (4c)*
h-1-t
k=0
S $(46)*=1 + (4c)². 2(4c) 53 (4c)a=--
2. OPT' = 4.
Σ
(4c)* S 4. (4c))
k=
The first incquality is since at any time t the optimal solution opens single facility and there are (4c)* clients that are at distance Σ (4c)* from the facility that is located in leaf of their subtree.
At time f = h, we have OPT" = 0.
On the other hand, we also observe that if at time 1, 1,..., h h the algorithm has xf + x S 1/2, then the algorithm's 's solution has cost at least 2c 2ee'. To see this, note that the two clients at n/. and Hh must be matched fractionally to extent at least 1/2 to a center outside the subtree rooted at r". Hence the cost paid by the algorithm is at least four times the cost of the edge between 1d and its parent -f1 which is at least
We next observe that if in round t = .h. - 1 if it holds that æi + æ < 1/2, then the algorithm pays a cost of at least c. OPT To see this, note that this condition holds then the set of clients at time must be matched fractionally to extent least 1/2 to facility outside the subtree of nt.
The service cost of this fraction is least twice the weight of the edge between u' and its parent, and hence the algorithm's 's service cost for these (4c) clients at time L. is at least
1
4- (4c)* 4(4c) > 2c OPT". 2
1
We conclude as before. Any algorithm maintaining ap- proximation better than 2c with respect OPT' must have at each time t = 1,...,AA h - 1 at least a 1/2 fraction of a center open in the subtree of r Since the algorithm can open at most one center at any given time, and by construction of the adversarial sequence, at every time t O..... h 1. the algorithm has more fractional mass in the child of r that is not p++1, the algorithm must open at least 1/4 of center to maintain a 2e-approximation. Hence the algorithm must open total of Ω(h) centers over the course of the phase, where we observe that size of the metric is n = 2 and the aspect ratio is = (((4c))). This sequence may be repeated.
(4c) 2. (46) =(Ac)= > c- 3(4c)=-1 e. OPT 2
Finally, we can conclude that any algorithm that maintains an approximation better than e with respect to OPT' must open at each time 1,.... h 1 at least 1/2 fraction of a facility in the subtree of u², By the construction of the adversarial sequence, it must also open at least 1/4 facility in the subtree in which there are no additional clients at time t+ 1. In total, the algorithm opens at least ا-م = 9(h)= = 2(min (log FI, log, A} facilities, where we observe that [F| = 2 and A = O(4c)). When the clients at time = h leave, the optimal solution does not have any facilities and
15

---

Competitively Consistent Clustering
Wip Moum' p
Mal
M m.
(a)
(b)
Figure 2. K- C-neteer Objective
Auidect
(a)
(c)
Figure 3. I-Center Recourse
Finally, suppose again that the algorithm is allowed to main- tain total mass of b-k = b facilities at each time step. Then, at the beginning of each phase, there exists a subtree of height/ = S2(h log, b) with total initial mass of at most 1/4. The adversary can restrict its sequence to this subtree and the algorithm, again, must open 1/4 of a facility in each level of the tree, paying total opening during the phase. Overall, the lower bound on the recourse competitiveness is [mmin flogin log, A} bogb).
existing data point was deleted with probability 1/10. We set = 4 (for k-center and k-median), B 3/2 and == 1/4.
In the objective plots, we plot the objective of our online algorithm over time (red), alongside the value of the frac- tional optimum OPT" each point in time (green), well B OPT' (blue), which theorems guarantee is an upper bound on the algorithms objective. In the recourse plots, we plot the recourse of our online algorithm over time (red), alongside the optimum fractional recourse without re- source augmentation (green), i.c. exactly &o centers, exactly 8 approximation. Finally, in the last set of plots, we track the number of centers opened by our k-center and k-median algorithms over time.
of Q(h log2 b)
D. Experiments continued
Each column below corresponds to one of these datasets ((a) Glass, (b) Wine, (c) Airfoil), and the data streamed online as follows for T 100 times steps. At each time either new data point was inserted with probability 9/10 100
16

---

Competitively Consistent Clustering
(a)
(b)
(c)
Figure 4. Facility Location Objective
(a)
(b)
(c)
Figure 5. Facility Location Recourse
Figure 6. k- M-Median Objective
17

---

Competitively Consistent Clustering
(a)
(b)
(c)
Figure 7, I-Median Recourse
0-255
k-center with 0.25 WINE
E-cemter with = 4,2 0.5 AIRFOIL SELF-NOISE
4.0
4.
33
3.3
3.5
100
20
60
130
(a)
(b)
(c)
Figure le-Center Number of Centers Over Time
kemedian with GLASS
k-medion
k-medinn with & 4. 025 ARFOLL SELF NOISE
4.2
3.2
Montee
2..0
1.
1.2
Time 2kx
Tite
Time Step
(a)
(b)
(c)
Figure 9, I-Mediaan Number of Centers Over Time
18


Reviews:
[{"review_id": "arjtugw2tR", "reviewer": "Reviewer_iX2S", "summary": "This paper studies fully dynamic clustering algorithms with competitive recourse guarantees. The authors focus on three classic clustering problems: k-center, facility location, and k-median. In the fully dynamic setting, given a metric space with n data points, a different set of points is chosen as clients at each time step. Then, the algorithm is required to maintain a sequence of clustering solutions over steps such that the clustering cost is approximately optimal in every step while minimizing the recourse, which is the total changes in the center set across steps. \n\nLet $\\Delta$ be the aspect ratio of the metric space and $F$ be a subset of facilities in the space. For every $\\beta \\geq 1$, let $OPT_\\beta$ be the optimal recourse of an offline solution that maintains $\\beta$ approximation. \n\nThey provide algorithms for these problems which satisfy: for every $\\beta \\geq 1$, and $\\epsilon \\in (0,1/2)$,\n\n- For k-center, it maintains an $O(\\beta)$ approximate solutions with $(1+\\epsilon)k$ centers while ensuring recourse at most $O(1/\\epsilon^2 \\cdot \\log |F| \\log \\Delta)OPT_\\beta$. \n\n- For facility location, it maintains an $O(\\beta)$ approximate solutions while ensuring recourse at most $O_{\\epsilon}(\\log |F| \\log \\Delta)OPT_\\beta$. \n\n- For facility location, it maintains an $O(\\beta)$ approximate solutions with $O(k)$ centers while ensuring recourse at most $O_{\\epsilon}(\\log |F| \\log \\Delta)OPT_\\beta$.  \n\nThey also provide the lower bound which shows that for any $\\beta \\geq 1$, any randomized algorithm that maintains an $O(\\alpha \\cdot \\beta)$ solution requires recourse at least $\\Omega(\\min(\\log |F|, \\log_\\alpha \\Delta)) OPT_\\beta$, moreover, for k-center and k-medians with even O(k) centers.   \n\nThey achieve the upper bound by leveraging the Positive Body Chasing framework, which provides fractional solutions that they round efficiently while preserving approximation and recourse guarantees. The paper presents both theoretical results with upper and lower bounds on recourse and experimental validation on UCI datasets, showing that the proposed methods significantly outperform the worst-case guarantees in practice.", "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": "Thanks for the thorough and very positive review. We fixed the comments, and will try to include a more formal proof of the remark. In Theorem 1.1 in the facility location and k-median, we already lose a constant in the cost (or the number of servers). Hence, one may simply use \\eps=1. We will add a comment on this.\n\nA static algorithm that does not care about recourse, and recomputes the solution from scratch at every time may have a very large recourse. Consider, for example, a dynamic 1-center problem in which there exists a single point that is a good center for all time steps. An offline algorithm that recomputes the solution may fail to detect this point and keep using a different point at every time step. We claim that the benchmark we use in our experiments is more stringent/informative. We compare against the fractional OPT (up to a constant slack factor beta which we set to 1.5); up to this slack factor, this is better than any offline benchmark. Furthermore, of all possible fractional OPT solutions, this is the one with the best recourse possible.", "claims_and_evidence": "Yes, the paper's claims are well-supported by both theoretical analysis and empirical results.  \nThey provide both upper bound and lower bound for the problems and run experiments to validate their algorithm on real-world datasets.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are appropriate.\n\nThey utilize the Positive Body Chasing to get a fractional online solution, and then provide rounding techniques carefully designed to balance approximation quality and recourse minimization. The experiments use benchmark datasets from the UCI repository. The evaluation criteria are reasonable and well-justified, with an emphasis on both approximation quality and recourse efficiency.", "theoretical_claims": "Yes, I checked the proof of all upper bounds and lower bounds in the paper and appendix. While I only briefly checked the positive body chasing framework to achieve the fractional solution in appendix A.", "experimental_designs_or_analyses": "Yes, I checked the validity of the experiments in the appendix.", "relation_to_broader_scientific_literature": "The paper is well-connected to broad research topics including consistent algorithms, clustering algorithms, and online and dynamic algorithms.", "essential_references_not_discussed": "No. The paper covers the necessary references.", "other_strengths_and_weaknesses": "Strength:\n- The paper proposes these interesting fully-dynamic clustering problems.\n- The paper provides interesting algorithms and gives theoretical analysis of the approximation on clustering cost and the total recourse. \n- The paper also provides the lower bound on the recourse approximation factor for the fully dynamic clustering algorithm by constructing an interesting instance with HST metric.", "other_comments_or_suggestions": "Minors:\n\n- Line 282, Proof of Lemma 3.3, I think $OPT^t$ should be $r_j$.\n- Line 355, Proof of Theorem 3.4, there seems to be a missing sum over all time steps t = 0,1,..., T.\n- In Theorem 1.1, What is the range of the parameter $\\epsilon$? Also, it seems from the later analysis, for facility location and k-medians, the approximation factor for recourse should have a dependence on $\\epsilon$ as well?\n- In Remark 3.2 and 3.5, I can get the intuition of the analysis. But, if there is space, I think it would be better to include a detailed analysis for one of them in the main body?\n-Maybe some experiments can be included in the main body, one or two figures due to the remaining space in the paper?", "questions_for_authors": "- In the experiments, you mainly test your algorithms, the fraction optimal solution, and the upper bound given by the analysis. Would it be interesting to compare your algorithm with some other traditional clustering algorithms which are static and do not care about the recourse at all (just recompute the solution at every time step)?", "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": "xehRWKBp30", "reviewer": "Reviewer_m98A", "summary": "This paper considers dynamic clustering problems, including dynamic k-center, facility location, and k-median.  The goal is to maintain constant factor approximation with small recourse (the total changes made to the solution).\n\nAll existing works in this problem obtain an absolute recourse guarantee, namely, they prove a bound on the total number of recourse. Authors observe that such worst-case bound often occurs in a pathological situation. However, in most natural cases, the optimal offline recourse can often be made much smaller. This motivates the study of algorithms with competitive recourse guarantees, which are popular goals in the dynamic setting. \n\nThe authors design algorithms with competitive recourse for all three clustering problems studied. The competitive ratio is logarithmic in the metric spread and the number of candidate centers. Specifically, their algorithm maintains a bicriteria approximation solutions for $k$-center and $k$-median, and a constant factor approximation for facility location, both with logarithmic competitive ratio.\n\nTechnically, the algorithm builds on a recent chasing positive body framework, with the development of certain rounding techniques to satisfy the recourse guarantees.\n\nMoreover, a lower bound is proved to show that the logarithmic competitive ratio is the best one can hope for, and experiments have been conducted to support the claims.", "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": "Thanks for the thorough and very positive review. In our comments to Reviewer 1 (iX2S), we argue that the fractional OPT against which we compare our algorithm is a the strongest possible dynamic benchmark (up to the constant slack factor of beta). See our comments to Reviewer 3 (G5B5) about the update time.", "claims_and_evidence": "The claims have been proved rigorously.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have not checked all the proofs in the appendix.", "experimental_designs_or_analyses": "Authors have implemented their algorithms to verify their claims.", "relation_to_broader_scientific_literature": "I think the problem studied is important in algorithmic machine learning. The main results of this paper may be interesting to anyone interested in clustering.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "strength: the result is novel with theoretical depth. \n\nweakness: Although the experiment has been conducted, it is mostly for the aim of verifying the recourse guarantee. It might be good to test against some natural dynamic algorithms as benchmarks to show practical value. So far, I think the main value of this result is on the theory side.", "other_comments_or_suggestions": "I have not found significant typos. The paper is written well.", "questions_for_authors": "What is the updated time of your algorithm?", "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": "uTJFTZ4WEw", "reviewer": "Reviewer_G5B5", "summary": "This paper studies fully dynamic consistent clustering, specifically focusing on the $k$-center, facility location, and $k$-median problems. Previous work has focused on algorithms maintaining solutions close to optimal while minimizing recourse—the number of changes to centers over time. The key innovation here is the consideration of a \"beyond worst-case\" scenario. The authors design algorithms that maintain approximate solutions with recourse bounded competitively against the minimal recourse achievable by an offline algorithm.\n\nThe main technique builds on the Positive Body Chasing framework recently introduced by Bhattacharya et al. [FOCS 2023], which provides fractional solutions to clustering problems. The paper's primary contribution is developing rounding methods to convert fractional solutions to integral ones while preserving approximation and recourse guarantees.", "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": "Thanks for the thorough review. Indeed, in the statement of Theorem 1.1, the result for the k-center is for every \\eps\\in(0,1/2). We will add this to the statement. Our algorithms are with 'resource augmentation' which is very common in competitive analysis (e.g. in caching, network routing, scheduling, see Chapter 4 of Beyond the Worst-Case Analysis of Algorithms by Tim Roughgarden for a survery), and Theorem 1.1 explicitly states this as an assumption. As reviewer 4 suggested, we will emphasize this more (also in the abstract).\nOne may also think equivalently about resource augmentation as allowing our algorithm to use at most k centers, but comparing our solution to an all powerful offline solution (that knows the future), but is only allowed to use slightly less than k centers. \n\nAs Reviewer 4 (Bgbi) notes, giving an algorithm that opens precisely k instead of O(k) centers is a worthy open question, but a mostly theoretical one: in practice the parameter k is usually selected heuristically, and users of such algorithms are often equally happy with a clustering with k' = O(k) clusters so long as it still explains the data well, doesn't overfit, etc. Finally, we have added experiments to our paper that show that in practice on our test instances, our k-center and k-median algorithms tends to open at most k centers anyway.\n\nAbout empirical comparison to prior work: in our comments to Reviewer 1 (iX2S), we argue that the fractional OPT against which we compare our algorithm is a the strongest possible dynamic benchmark (up to the constant slack factor of beta).\n\nAbout the update time: Our main concern in this paper is the recourse. Note that already the update time for maintaining the fractional solution (Bhattacharya et al. [FOCS 2023]) may be polynomial. A naive implementation of our rounding algorithm requires poly(n,k) update time, where n is the number of clients at the time step. We believe such an update can be done quite efficiently, but still at least in linear time. Designing an algorithm with competitive recourse and also fast update time is indeed an interesting distinct research question.", "claims_and_evidence": "Proofs support the theorem statements. The paper explains high-level proof techniques quite clearly, and to my best comprehension, the proofs presented in the main body and appendix are correct.\n\nHowever, there is one important concern about consistency in the problem definition. The paper considers clustering formulations ($k$-center, facility location, and $k$-median), typically defined with at most $k$ centers allowed. Yet, in Theorem 1.1, the proposed algorithms use $(1+\\varepsilon) \\cdot k$ or even $O(k)$ centers, where $\\varepsilon \\in (0, 1]$. This contradicts standard definitions in the literature, where dynamic algorithms strictly maintain exactly $k$ centers (e.g., Łącki et al., 2024; Bhattacharya et al., 2024). Allowing extra centers makes the problem strictly easier, possibly trivializing it, as one could achieve approximation ratios smaller than 1 for the $k$-center problem by opening additional centers. I realise this issue is acknowledged briefly in the conclusion, but it should be justified and explained more clearly.", "methods_and_evaluation_criteria": "The experiments compare the proposed method against the optimal fractional solutions and the theoretical bounds stated in the theorems, which is appropriate. However, the paper lacks experimental comparisons to previous methods from the literature, such as \"Efficient and Stable Fully Dynamic Facility Location\" by Bhattacharya et al. [NeurIPS 2022], which implemented a related algorithm for dynamic facility location.", "theoretical_claims": "I checked all proofs and found no issues.", "experimental_designs_or_analyses": "From the text the experimental design seems sound and valid. I wanted to check the code as well, but unfortunately no supplementary material was provided.", "relation_to_broader_scientific_literature": "This paper contributes to the growing body of work on dynamic clustering and online approximation algorithms. Previous work on fully dynamic clustering focused on absolute recourse, e.g., Łącki et al. (2024) and Bhattacharya et al. (2024). In contrast, this work introduces the notion of competitively consistent clustering, aligning itself with recent trends in the broader literature that advocate competitive analysis against optimal offline recourse. This competitive recourse perspective originates from Bhattacharya et al. [FOCS 2023], and the current paper is (to the best of my knowledge) the first to effectively extend this framework to classical clustering objectives through tailored rounding schemes.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "S1) I think the overall proof techniques are quite nice. Combining the Positive Body Chasing framework with the different rounding mechanisms is nice, and I could see it having potential future impact.", "other_comments_or_suggestions": "1. line 036, right column: Can use \\citet to reference Lacki et al. (2024). Also on line 085, right column, among other places.\n2. In Theorem 1.1, $\\varepsilon$ is not defined.", "questions_for_authors": "Q1. In the introduction you describe the problem as: $k$-center, in which we can open _at most_ $k$ centers (...). However, in the statement of Theorem 1.1, your maintained solution uses $(1+\\varepsilon) \\cdot k$ centers. Since $\\varepsilon \\in (0, 1]$, this means your solution uses potentially $2k$ clusters. However this is different than the formal problem description (see the Claims and Evidence section above for more elaboration). Could you please clarify this, in case I misunderstood something.\n\nQ2. Could you please elaborate on the update time of each algorithm? Your proposed method has low recourse, but I'm curious about the guarantees on the running time of each 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": "tfeaNg433W", "reviewer": "Reviewer_Bgbi", "summary": "When clustering dynamic data (with insertions and/or deletions), consistency of updated solutions is a  concern that can be more relevant that optimal cost in practice. This work studies fully dynamic clustering algorithms for k-center, facility location, and k-median with competitive recourse. For fully dynamic inputs, the pathological example that required linear recourse inserts and deletes the same $O(1)$ points over and over again so that the value of an optimal solution oscillates between two magnitudes. Let $OPT^\\\\beta_R$ be the recourse of an optimal offline algorithm with multiplicative cost approximation guarantee $\\\\beta$ for the problem at hand, and $\\\\Delta$ be the aspect ration of the input. The authors obtain the following dynamic algorithms:\n\n1. For k-center, a bi-criteria approximation that uses $(1+\\\\alpha)k$ centers and has multiplicative $O(\\\\beta)$ cost approximation with recourse $O(\\\\log n \\\\log \\\\Delta / \\\\epsilon^2) OPT^\\\\beta_R$.\n2. For facility location, it maintains a multiplicative $O(\\\\beta)$ cost approximation with recourse $O(\\\\log |F| \\\\log \\\\Delta) OPT^\\\\beta_R$, where $F$ is the possible set of centers.\n3. For k-median, a bi-criteria approximation that uses $O(k)$ centers and has multiplicative $O(\\\\beta)$ cost approximation with recourse $O(\\\\log n \\\\log \\\\Delta) OPT^\\\\beta_R$.\n\nThe authors also show that at least one of the logarithmic dependencies is required and conduct experiments in the appendix.\n\n## update after rebuttal\n\nThe authors addressed my questions and could clarify my doubts. I adjusted my scored accordingly.", "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": "Thanks for the thorough and very positive review.\n\nWe will mention in the abstract that the algorithm are bi-criteria. Indeed, theoretically, the gap between a solution that uses k and k+1 centers may be large. However, we believe this rarely happens in practical instances.\n\nThe rebuttal platform does not allow for us to upload new plots, but we have added the plot of # centers opened as a function of time to our manuscript. In both our k-center and k-median experiments, the algorithm almost always opens no more than k centers.\n\nWe did not think about the k-means objective. This is indeed a great and interesting future research problem.", "claims_and_evidence": "All claims are backed by proofs.", "methods_and_evaluation_criteria": "Rigorous theoretical analysis combined with experiments is a very reasonable approach.", "theoretical_claims": "Checked plausibility of proofs in the main part and skimmed through the appendix for completeness.", "experimental_designs_or_analyses": "The extent of the experimental setups (3 datasets, one choice for k) is a bit limited, but the setup itself is appropriate.", "relation_to_broader_scientific_literature": "Consistent clustering of dynamic data is an emerging topic in theory, and inherently important in many practical applications.", "essential_references_not_discussed": "None identified.", "other_strengths_and_weaknesses": "The paper introduces algorithmically nice and simple, but analytically non-trivial rounding schemes on top of a known algorithm for maintaining dynamic fractional solutions by Bhattacharya et al. By using competitive recourse, the authors show that one can circumvent the trivial worst-case bounds for fully dynamic algorithms and optimal close(r) to optimal recourse.\n\nOn the other hand, bi-criteria solutions that use $O(k)$ centers that are compared to offline algorithms that use $k$ centers open a new gap. E.g., consider k-center and $k+1$ input points (or clusters) at large distance. While an optimal solution needs to pay the distance at least one, an algorithm that uses $k+1$ centers can achieve cost 0. Nevertheless, not using exactly $k$ but $O(k)$ centers is a concern that often lies mostly on the theory side of the problem.", "other_comments_or_suggestions": "It seems appropriate to mention in the abstract that the algorithms for k-center/k-median actually compute bi-criteria approximations.\n\nWhenever $k'$, it may be worth to consider if it's useful to mention its best known value as derived from the analysis in appendix A.", "questions_for_authors": "1. Can you add plots that show the actual number of centers that the dynamic algorithm opened?\n\n2. Can the k-median results be extended to k-clustering (e.g., k-means)?", "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": {}}]

Author rebuttal:

Meta-review: The paper introduces competitively consistent clustering for fully-dynamic k-center, facility location, and k-median problems, aiming to maintain approximately optimal solutions while minimizing recourse compared to the optimal offline recourse. The authors design algorithms using a reduction to the positive body chasing framework, providing fractional solutions which are then rounded. Nearly matching logarithmic lower bounds are also provided.   

This work proposes interesting solutions for fully-dynamic clustering problems and so it would be a good addition to the conference program. The techniques are quite nice, particularly the reduction to positive body chasing and the subsequent online rounding methods. Furthermore, the paper's claims are well-supported by both theoretical analysis and empirical results. A minor weakness is that although the experiment has been conducted, it is mostly for the aim of verifying the recourse guarantee, and perhaps could be expanded slightly to show performance regarding the clustering objective itself more directly.
Decision: Accept (poster)