Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces
Authors: Leyla Biabani
Annika Hennes
Denise La Gordt Dillie
Morteza Monemizadeh
Melanie Schmidt
Venue: NeurIPS 2024 poster (2024)
Keywords: $k$-center with outliers
fully dynamic model
metric spaces
Primary area: optimization
TL;DR: We propose a novel fully dynamic algorithm that maintains an $(4+\epsilon)$-approximate  solution to the $(k,z)$-center clustering that covers  all but at most $(1+\epsilon)z$ points at any time in the sequence.

Abstract: The metric $k$-center clustering problem with $z$ outliers, also known as $(k,z)$-center clustering, 
involves clustering a given point set $P$ in a metric space $(M,d)$ using at most $k$ balls, 
minimizing the maximum ball radius while excluding up to $z$ points from the clustering. 
This problem holds fundamental significance in various domains such as machine learning, 
data mining, and database systems.

This paper addresses the fully dynamic version of the problem, where the point set undergoes continuous updates (insertions and deletions) over time. The objective is to maintain an approximate $(k,z)$-center clustering with efficient update times. 
We propose a novel fully dynamic algorithm that maintains a $(4+\epsilon)$-approximate 
solution to the $(k,z)$-center clustering problem that covers 
all but at most $(1+\epsilon)z$ points at any time in the sequence with probability $1-k/e^{\Omega(\log k)}$. 
The algorithm achieves an expected amortized update time of $\mathcal{O}(\epsilon^{-2} k^6\log(k) \log(\Delta))$, and is applicable to general metric spaces. 
Our dynamic algorithm presents a significant improvement over the recent dynamic $(14+\epsilon)$-approximation algorithm by Chan, Lattanzi, Sozio, and Wang for this problem.

Improved Guarantees for Fully Dynamic k-Center Clustering with Outliers in General Metric Spaces
Leyla Biabani
Annika Hennes
Eindhoven University of Technology Eindhoven, The Netherlands
Heinrich Heine University Düsseldorf
Düsseldorf, Germany annika hww.ee@hhueuu..mm.mm.o....h..... de
1. biabani @tue. nl
Denise La Gordt Dillie Eindhoven University of Technology Eindhoven, The Netherlands Iagoratad1leedeniss@@aaall com
Morteza Monemizadeh Eindhoven University of Technology Eindhoven, The Netherlands
m. D..monemizaeh@@tue .nl
Melanie Schmidt
Heinrich Heine University Düsseldorf Düsseldorf, Germany
aschmidt@hhu. de
Abstract
The metric k-center clustering problem with outliers, also known (k, ceeeter clustering, involves clustering given point set P a metric space (M, d) using most & balls, minimizing the maximum ball radius while excluding up = points from the clustering. This problem holds fundamental significance various domains, such machine learning, data mining, and database systems.
This paper addresses the fully dynamic version of the problem, where the point set undergoes continuous updates (insertions and deletions) over time. The objective is to maintain an approximate (k:, =)-center clustering with efficient update times. We propose novel fully dynamic algorithm that maintains a (4 + e ->aaproxxmmtee solution to the (k, 2) -center clustering problem that covers but at most (1 + <)z points at any time in the sequence with probability 1 k/o R) The algorithm achieves expected amortized update time of (Ee-565 log(k) (k) log(A)), and is applicable to general metric spaces. Our dynamic algorithm presents a significant improvement over the recent dynamic (14 aapproxximtioon algorithm by Chan, Lattanzi, Sozio, and Wang [5] for this problem.
Introduction
Clustering problems and algorithms play an important role across a multitude of fields, helping researchers and practitioners in the analysis of data and identification of patterns. These techniques find extensive application in diverse domains, including machine learning, where they help in categorizing and understanding complex datasets. In data mining, clustering methods utilized to uncover hidden structures and relationships within large datasets, facilitating better decision-making and insight generation. Moreover, in image and signal processing, clustering algorithms assist in segmenting and classifying data, enabling tasks such as image recognition and signal denoising.
In bioinformatics, clustering techniques essential for organizing biological data and identifying patterns genetic sequences, protein structures, and gene expression profiles. Similarly, anomaly
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

detection, clustering methods are employed to identify unusual or unexpected patterns in data, which may indicate potential anomalies or security breaches. Furthermore, in social network analysis, clus- tering algorithms help in understanding the structure and dynamics of social networks by identifying communities and influential nodes.
The k-center problem is known as one of the fundamental clustering problems. Given a set of points P in a metric space and a number k, the aim of the k-center problem to find & centers such that the maximum distance between any point and its closest center is minimized. This can also be equivalently formulated as finding a minimum radius r and centers cI.....C0 Ck such that the balls B r) cover the point set. The k-center problem can be 2-approximated, and this is the best possible approximation guarantee [[3]. In the last decade, the focus has shifted to analyzing the problem under various complications that arise in applications.
One line of research is study the k-center problem (and other clustering problems) in different computational models like streaming or for dynamic point sets. In the first case, points arrive sequentially, and only summary can be stored in memory. In the second case, the point set is maintained by insertion queries and deletion queries for single points, and algorithms have to update their solution after any such query.
Another line of research is to study clustering under constraints. For example, capacitated clustering is very popular, i..., limiting the number of points per cluster. However, lower bounds on cluster sizes have also been studied in the context of anonymity, and newer works have also considered constraints that model societal concerns like fair or diverse composition of clusters. In this paper, we study clustering with outliers. Formulated as a constraint, the k-center problem with outliers allows k + 2 centers, but of these have to be singletons, meaning no point may be assigned to them. We can intuitively formulate it with balls as follows: The k-center problem with outliers asks to find a minimum and centers CI...., Cg such that the balls Bp r) cover all but z points.
Solving clustering problems in the presence outliers is a crucial task due to the common occurrence of measurement errors or other sources of significant deviation from the rest of the data in real- world datasets. Ignoring outliers can severely distort the results of clustering algorithms, leading to inaccurate groupings. To address this challenge, a common approach is to solve a clustering problem while excluding up to z data points considered as outliers.
The first approximation algorithm for the k-center problem with outliers is due to Charikar et al. g The challenge when designing approximation algorithms in the presence of outliers is that one needs to show that enough points are covered by balls of bounded sizes around the approximate centers. It is not necessary to identify the outliers of an optimal solution exactly as long as the number of uncovered points remains small enough. Due to this, [8] and follow-up papers use charging arguments. Points covered by the solution of the algorithm are mapped to points in optimum clusters, and it is then shown that the number of uncharged points is small enough.
We explore the k-center clustering problem with 2 outliers within the fully dynamic model, where the point set experiences continuous updates through insertions and deletions over time. Quite some work on this problem has been done for inputs from metric spaces with bounded doubling dimension [2] 3 19. This setting allows for geometric data structures that allow easier navigation through the data set and also bounding of the number of changes that can occur due to a query by dimension-dependeent volume arguments.
We study the general metric setting. General metric spaces represent key objective for clustering algorithms due to their broad range of distance functions, ensuring applicability to any data type. Chan et al. recently showed that in general metric spaces, any dynamic (11) Lpproooxxiittoonn algorithm for k-center clustering excluding at most outliers has an amortized update time of ?(2) [5]. For real-world applications, the fraction of outliers of the data could be arbitrarily large. Therefore, we allow for (1 + <)= outliers to be excluded to avoid the dependence on of the update time.
The only previous work in this setting is the algorithm by Chan al. (5) which returns solution with at most (1 + e)z outliers with probability at least 1 - 8, for 0 < 8 < and > 0. It works by maintaining a clustering with t := h [lg 4 clusters of radius 2r and using this to derive a final clustering with & clusters and radius 14r. They maintain such a clustering for all r E I' := {(1 7)² dmin < (1 + 7)² < (1+ dmax, i E NJ. with dmin and dmax the minimum and maximum distances, respectively, between any two points ever inserted. It is then shown that there exists instance E I that will approximate the optimal radius to within factor (14 + 7).

---

while allowing for (1 + 2)2 outliers, with probability at least 1 - 8. The amortized time per update is ((1) 1 log" }), with [I'] (log dum
den /TT. The total memory requirement ((1)) (ma)) where is the number of points in the current set.
1.1 Our contribution
We introduce novel fully dynamic (4 + e) appproxiiatio algorithm designed to maintain h-center clustering while allowing for at most (1 + <)2 outliers at any time in the sequence.
The expected amortized update time is (6=3a log(k) log( ()) per operation (insertion or deletion). This independent of 2 and of the number of points currently present in the sequence. This characteristic makes the algorithm applicable to real-world scenarios.
Notice that our data structure is continually storing an actual solution, so we can produce this solution at any time and do not need to specify additional query times (like, for example [9] 18).
Our main technical contribution is a novel combination of the sampling- level data structure by Chan et al. [5] and the original greedy strategy by Charikar et al. [ that enables us to achieve a much improved approximation guarantee compared to [5]
Theorem 1.1. Let (M,d) d) be metric space and > O be an accuracy parameter. The spread ratio
A dmsa dynamic algorithm that maintains a k-center solution that allows up to (1 + c)z many outliers on the current set of points. At every point in time, the current clustering a (4 epppppoxiimaioon to an optimal solution for the (k, ccecter problem with high probability. Upon insertion or deletion of point, the data structure is updated in amortized update time O -3 (k) log(A)).
daii of all points ever inserted is assumed to be bounded. There exists randomized fully
To achieve this, we make use of a data structure that is described in Section 2.1 and maintained by the respective algorithms handling updates to the point set. The algorithm handling insertions specified in Section 2.2 and the deletion algorithm is described in Section 2.3 Similar to the approach by Chan et al. [5]. we maintain a hierarchical structure consisting of levels, each containing one cluster. Unlike their work, however, we only maintain < k levels. For the correct radius guess, the union of these levels directly gives the desired (4 + e>aappooximation. If a level violates certain properties, this and all higher levels are reclustered. As opposed to [5]. we do not need to recluster every time center gets deleted but only when a cluster does not contain enough points anymore. The algorithm handling the reclustering described in Section 2.4
Our analysis of the approximation ratio follows a similar argument as the proof of the 3-approximation for static k-center with outliers as given by Charikar et al. [8] and works by charging points from chosen clusters to points optimal clusters. We follow the same iterative charging method but extend their approach by maintaining set of artificial outliers in order to adjust the argument to our algorithm specifically.
Note that we assume that a center can be any point from the underlying metric space, if the point was present in the data set once. Requiring that centers can only be placed currently active points, we can achieve a 6-approximation. We formalize this in Lemma G.1
1.2 Further Related work
The k-center problem is very well understood; two 2-approximation algorithms for it are known [3] 15] and a matching lower bound is also known [6] The k-center problem with outliers was first studied and 3-approximated in [8]. In 2016,
4 gave 2-approximation for this problem, but
the algorithm is rather complex and less amenable practical implementation. Charikar al. developed an elegant algorithm to maintain an 8- 8-approximation for the vanilla k-center problem in the streaming model. Streaming can be seen as a dynamic insertion-on only model. McCutchen and Khuller [17] improved this algorithm to a (2 + approoxxianioonnn and also extended it to (4 + apppoxxximmti for k-center with outliers. The k-center problem with outliers has also been studied in the sliding window model [10 18 that also bears some similarity with our setting. For bounded doubling dimension, [18 gave a + +3+ approximatan,,, but the algorithm for the general metric case is only stated as apprxxxpxxnnnnoion..

---

The fully dynamic k-center problem without outliers in general metrics was studied by 16 and the best-known result is by Bateni et al. []] The same paper also shows that any algorithm that provably satisfies non-trivial approximation guarantee needs (nnk) queries to the distance function, i.e., the amortized update time is in (k)),, making their algorithm close to tight. The fully dynamic k-center problem without
with an amortized update time of O polyyoogn A))
outliers was also studied for metrics with bounded doubling dimension [14 19 12]
and in Euclidean
space [20].
1.3 Preliminaries
In the preliminaries section, we provide introduction to the (k:, -)eentr problem and discuss the dynamic model used in our paper.
We study the k-center clustering problem with outliers, formally defined as follows.
Definition 1.2 ((k, z)-center clustering). Let P be point set in metric space (M, d) and let k, E N be two parameters. The goal is to compute a set C' C M of size at most k, such that the maximum distance of all but at most points to their nearest e C' is minimized. That is, find C such that minzgr.jzis m my miz min.ec d(z, c). with |C|| s k.
We define din and dmax as the minimum and maximum distances, respectively, between any two points ever inserted. The ratio A dax is referred to as the spread ratio, and is assumed to be bounded. Let TOPT be the optimal radius for the (k, =ceenter clustering problem of a point set P. We also define the ball (c, = {p P: d(c, p) S r to be the set of points in P that are within distance from c. is clear from the context, we may drop P from the definition (p r). For a non-negative integer m, we denote {1, m] by [m)]
duin
In the version of the (k. z)-eeneer clustering problem that we consider, we allow (1 + c)2 outliers instead of strictly 2. Furthermore, we require centers of clusters to be in the metric space (M, d), but they need not be currently present P. This is referred to as the non-discrete version of the problem. Lemma G. in the Appendix shows how our data structure can also support the discrete version of the problem and provides a 6-approximation solution for
Fully dynamic model. We consider the (k, z)-eentr clustering problem in the fully dynamic model against an adaptive udversary. In this model, we start with an empty point set, p= 0, and process a sequence of operations determined by the adversary. We assume the adversary does not know the random bits chosen by algorithm; however, it can observe the algorithm's 's output and adapt its responses in real time (unlike an oblivious adversary, which fixes a sequence of operations in advance). Each operation added to P, or a deletion, where a point currently in P is removed. We assume only points currently in P may be deleted. Let P represent the point set P after t operations. In other words, pt consists of all points in (M, d) that have been inserted but not deleted after / operations.
be either insertion, where point from the metric space (M, d) is
2 Algorithm
To explain the main ideas of our algorithm, start by describing iterative offline algorithm, which gives a (4 + e) approximation for the (k, 2)-enter clustering problem.
Offline algorithm. We start with a point set P1 = P, 6 0 and parameters kt 2, E N. Here, r is fixed guess for the optimal radius. For each iteration we sample a set of S, P. of |S|| = the -h log k points with replacement, uniformly at random. Here, vé 2 63 is a constant, where 3 >
are constants. We find point e; E S. such that B(c, 2r) covers at least Ø points from P., where & is some threshold to be defined later. We then create new cluster C; Bp, (c;, 4r), let P++1 = P, and continue to the next iteration. We stop once k clusters have been created or P. = 0. Let X be a random variable representing the number of iterations we complete, where À can at most k. After we have done À iterations we have computed clusters C₁ C2...., CA with corresponding centers Cı C2, ..., CX. The points that are not covered by the union of these clusters will be the set of outliers that our algorithm reports. the set of outliers is at most (1 + <)z points, we can report solution for the (ks 2) ceeete clustering problem. This offline algorithm will be used as

---

sub-routine for the fully dynamic algorithm, which will be explained in Section 2.4. The definition of and the pseudocode of the algorithm will also be given that section.
Guesses for unknown TOPT- Since the optimal is usually known, for all E R = ((1 + c)² dmin S (1 + <)' I (1 + <) dmax, N). We then choose the
run the algorithm
smallest R such that all but most (1 c) points are covered. We will show that this gives
(4 + apaapproximation
Outlbors
Lends
Level 2
Level
Figure 1: The levels constructed by offline algorithm.
Leveling, We can visualize the output of this algorithm as (at most) À + 1 levels, where the first levels each represent cluster, and the last level represents the outliers (See Figure T.. More precisely, level represents cluster C with center which was created in the 5th iteration. Note that the construction of level only considers the points in P. which does not include points the lower levels {1, i-
The main idea for the fully dynamic algorithm maintain each level for [A arbitrary number of insertions and deletions by updating the cluster C; when necessary. In the rest of refer the level and superscript to refer the time. For example, P. refers to the points present in level at time t, and OPT refers to the optimal radius at time t. If the level or time clear from the context, these may be omitted. For instance, if we define a situation at time f', we will not repeat the superscript E' on every term.
+ 1] under an
the paper, we use subscript
2.1 Data structure and invariants
We will construct clustering Ci....,Cr of the current set of points P that store in the data structure D, introduced by 16). If is clear from the context, we will just write for Pt. As we do not know the current optimal radius, we will maintain one data structure D, for every choice of r E R = {11 + +)*= dmin S (1 + c)' < dmax, E N]. Every data structure consists of up to cluster-levels, with each level containing cluster Cj. In level we keep track of the set of the points P; currently not covered, i. e., P: = Ujzs Cj. Level X + contains the outliers, i.e.,
Z, = P Us We denote n, P. By (Bp,r) r) we denote the ball with radius r centered at for AC P.
and BA r) B(p,r)
Let a: 2 1. The data structure D, consists of the following components:
@ A list F, = {c1, C2, ..., C of A < k centers.
2 A list L, = (C,, C2,... Cx} of clusters with C; = By, (c;,4r).
@ A set Z, = P (ULEj C:) of outliers such that for all i E [사] and x E Z,, d(x,c) > 4r.
Let be constant. We have the following invariants for D,,.
Level invariant: for all P.+1 PA,., with C, Br, (c, 4r).
Dense invariant: for all e E Fr, 1Br, (c,, 2r) min ( 1, mi-
k-141 ok
5

---

2.2 Insertion
When new point p is inserted at time t, Procedure in the appendix executed. As imput, we have D, at time t, E (M, d). > 0 and 2, k E N. First, we check whether p is inside one of the existing clusters, in which case we can add p to such cluster. Otherwise, we add p to Z,. Next, we check the dense invariant is maintained after the insertion of the new point. Generally, the dense invariant can be broken two ways:
If the insertion of new point results more than (1 + e)= outliers, then Lemma 3.7 shows that the dense invariant is no longer valid at some level i.
If the addition point p to a cluster C₁ causes the dense invariant to be violated at some lower level j i. that occurs because n = nj
If the dense invariant is broken for some level i, we recluster levels i.... À with À s k by invoking Procedure 5 as a sub-routine, Observe that if there are multiple levels where the dense invariant broken, we choose the lowest one.
2.3 Deletion
For the deletion of point p at time t, Procedure ij the appendix is executed. The input is Dr at time t, E (M, d), e > and z, k E N. First we check if p is an outlier, in which case we remove p from Z,. If p either center or point in cluster, we find cluster C; which contains If cluster
points, we do not re-cluster and simply remove from C,. Note that the underlying point set exists the metric space (M, d). If the center G of cluster C; is deleted, provided that the dense invariant remains valid, we can continue utilize G as the center of cluster C. given our knowledge that the point c; is located within the metric space (M, d). In Lemma G.1 explain how
C = BBc, 4r) contains at least min 1, 1-
E2 axk
still obtain 6-approximation if centers have come
from the current point set. If [C,] < min 1, Pi-=
after the deletion of p, then it also 1- ax
follows that [ic,, 2r) n P.l < min (z 1, P1--2 1-14 ak i.e., the dense invariant is violated on this level. In this case, we want to redistribute the points in P, such that the levels i,..., fulfill the dense invariant. Deletion of a point in level does not violate the invariants at levels 1,..., 1. We re-cluster the points in (Uisis&Cy) U Z, using Procedure We finish by updating D,..
2.4 Clustering sub-routine
The clustering sub-routine is the offline algorithm that was described at the beginning of Section 2 The pseudocode of this sub-routine shown Procedure We use it to iteratively build the levels of data structure D,.. Two cases are distinguished based whether z is small or large compared to the number of points level line 4, 1 is constant with v 2 63, where > Ot, and a the constant used in the dense invariant. The threshold & that was introduced in Section different depending nu
n on the size of compared to n,, If + S a(k-r41). then @ = 2(k 2(k-i11) and if > a))
then d
If we find multiple points p" in line 6 or 12 we choose one arbitrarily. BK
2.5 All aspects combined
The first step will be to initialize all D,, such that C,, = 0. Then, the algorithm waits for an insertion or deletion operation. a point inserted, Procedure is is executed, and if point is deleted, Procedure 4 is executed. The algorithm is ran simultaneously for all E R {(1 + e)* dmin S
(e+ < +) dmaxs² i Nj.
In the next sections, it will be shown that a (4 (4+6 appprooximationn is given by the clustering C, with r E R the smallest for which |zz|| < (1+e) e)z.
3 Analysis
We begin our analysis of the dynamic algorithm by introducing the concept dense cluster and specifying the criteria for valid solution.

---

Definition 3.1 (Dense cluster). A cluster Bp, (Ca, 4r) is dense with respect to point set P, if it satisfies the dense invariant. That is, BB,, (c;, 2r) 2 min + 1, k-1+1
ax
Observe that for the dense invariant, we consider the ball By (c,, 2r) with a radius of 2r. However, a cluster (as seen in line 18 of Procedure corresponds to the points within the ball By, (c,, 4r), which has a radius of 4r.
Definition 3.2 (Valid solution). A solution Bp, (ci, ur.. Bp, (cx, 4r) with À S k for point set Pi is valid if it covers all but at most (1 + e)z points from Pt. We refer to each cluster Bp, (cg, 4r) for j E { of a valid solution as a valid cluster.
Lemma 3.3 (Running time offline algorithm). The running time of the offline algorithm, shown in Procedure is O(n 11 log(k:)), where n = IP).
Proof. In each iteration of the while-loop, we need to compute [B(p, 2r) for all p E S, Since |S,] = O( 222 log k), this takes Onne k2 log k) time. There can be most k iterations of the while-loop and hence the total running time is O "ieee"k-looo k).
3.1 Maintaining invariants
In Supplementary Section B, we prove the following three lemmas. Lemmas the dense and level invariants are maintained during the insertion or deletion of a point, respectively. Additionally, Lemma 3.6 shows that both invariants are maintained when invoking Procedure as subroutine upon the insertion or deletion of an arbitrary point with high probability if 2 TOPT- The case where r < TOPT is considered in Lemmas E. and E.2
3.4 and 3.5 show that
Lemma 3.4 (Procedure maintains invariants). Assume that time t, have point set Pt, data structure D, = (F,, Zr.) Z.). We assume that the level and dense invariants hold at time t and T 2 TOPT. At the start of time t + 1, we insert point p using Procedure 3 After the insertion, the level and dense invariants still hold with probability 1 if Procedure 5 was not called and with the probability of at least 2(k-i+1) where 2 1 if Procedure was not called.
Lemma 3.5 (Procedure maintains invariants). Assume that at time t, we have point set Pt, instance D, = (Fr, Ly. 2r). parameters k, E N Nnd >> We assume that the level and dense invariants hold at time and r 2 TOPT- At the start of time + 1, we delete an arbitrary point p using Procedure After the deletion, the level and dense invariants hold with probability I if Procedure was not called, and with probubility
2(k-i+1) with V if Procedure 5 was called. T
Lemma 3.6 (Procedure maintains invariants with high probability). Suppose the level and dense invariants hold for all levels < i and we call Procedure 3 on P. as the result of an insertion or deletion. Let À S lo be random variable representing the number of levels we have after completing Procedure 5 I 2 TOPT, Procedure 3 maintains the level and dense invariants for all levels j with
i S X with probability at least 2(k- with 1 > 1.
log
3.2
Approximation guarantee
Next, we prove that if the invariants hold, our data structure D, = LFr 2,, contains a valid solution to the k--center with outliers problem. Furthermore, if < (1++)rorr) Dr provides (4+ e)-approximation. Without loss of generality, for simplicity we assume that D, contains k levels. The proof of Lemma 3.7 follows the structure of the proof given in [8]. This proof uses the greediness of the algorithm to argue that the balls in the solution cover enough points to charge to. Here, we have to modify the proof to work with the dense invariant.
Lemma 3.7 (Approximation guarantee). Let P be the current point set. Assume that the level invariant and the dense invariant hold for all levels i S k. Then we have the following guarantees:
① Valid solution: TOPT S then B(ci, 4r) U. U...U.((C, 4r) covers all but at most (1 + 5)² outliers in P.
Approximate solution: If rorr S < (1 + e)rOPt, then Bicr, 4r) U...U Bick, 4r) gives (4 + approximmatio for the k-center with z outliers problem on P.
7

---

Proof. Recall that the level invariant states that for all i, we have P.+1 = P. 4r) and the dense invariant states that for all i, we have that [B(c,,2r n n.l 2 min(2 + 1, k-1+1 oxk
Assume that in the optimal solution, we have balls O Ok with radius S TOPT. The union of these balls covers all but 2 points in P. In order to prove Part D, we aim to charge all but at most = points of the optimal solution to points in our solution [c1,, 4r) U...U B(ck, 4r). We prove this by induction, and Part @ will then follow easily. In order to construct the charging argument, we need to argue that there are enough points in solution to charge the points in the optimal balls. To this end, we construct modified optimal balls Oz,..., O₁ where O C O; for every i I k.
For the base case, we have 0j = O1, ... , ,0, OR- We will show that we can order the modified ss i points from the first i modified
balls in such a way, that at the end of time step i, all but at most ak balls are charged to distinct points in B(c1, 4r) U... .... U B(c, 4r). This will allow to prove that our solution covers at least as many points as the optimal solution.
Assume that all but at most ak (i - 1) points in the first i 1 modified balls Of U U...00,__ have been charged to distinct points in B(c 4r) U... ... B(c;-1, 4r) and consider iteration é. We distinguish two cases, namely if B(c1, 2r) U... U Bie, 2r) intersects one of the remaining modified balls, or if does not. The charging argument for each case proceeds as follows:
Case 1. Case is when Bic,, 2r) U........ U... . (cG, 2r) intersects a remaining modified ball, call this ball O Note that O will be covered entirely by B(e1, 4r) U... U ((c, 4r), since r 2 rOPT. Hence, we charge the points of O2 to themselves and mark these points as covered. (See case 1 in Figure 2 We call this charging rule I. Since the modified balls are disjoint | any point can be charged only once (to itself) by this rule. Next, we update 0₁, Oz..... O..
Br)
B(g,
Ble, 2r)
BB.. 2.)
F
2r
TOPZ
P
B(c, 2r)
00 1-1
(Cass 1)
(Case
Figure 2: Visualization of charging rules and II. For case 1, we see that Blc; 2r) and O₂ intersect. As a result, B(c, 4r) covers all points in O, Points q are in set Z,. For case 2, the balls B(c,, 2r) and B(c2,2r) do not intersect the optimal cluster O. The crossed points in O²2 are charged black squared in Bec², 2r). The circle points in Og are not charged to any point. Points a, b, c are in z
We maintain two sets of credit points that we save and may use for future charging purposes. First, the set Z B(c, 4r) U... U which is the set of points covered by B(c,, 4r) that are not covered by Of U U. U...UO, O We let 2 [ be the number of such points. In Figure 2 points p. q are such points. Observe that no point is charged to points in Z allowing us to use them later. We refer to these points as credit points.
There may also be previous modified balls Oj, with j i that were considered in case 2 and are still present in P. More specifically, let Z be the set of (there may exist) points in O n B(c,, 4r) that have been charged to distinct points in Bic,, 4r) (See the discussion of case 2, below). For example, points a, b, e in case of Figure 2 Let 2 / be the number of such points. Since no points
In fact, original balls O,, On can overlap, but we can make them disjoint by assigning any point that is inside multiple balls to just one of them arbitrarily.
8

---

are charged to points in Z we save them as credit points for future charging purposes. We now update O1, Oz...., O2 as follows: Oz..., O stay the same and we define 2. + 2 artificial outliers in (0/+1 U U... (.,.
Case 2. Case 2 occurs if (c1, (r)J....BB... 2r) does not intersect any of the remaining modified
balls. See Figure 2 Let Of be one of the remaining modified balls covering _ _0-=2 points. Note that for finding O we do not count points that have been defined as artificial outliers, since these artificial outliers are already covered by balls of radius 4r in previous levels and we do not cover them by the remaining modified balls. We prove in Lemma 3.8 that such a ball O2 exists.
Æ-++1
Using the assumption of this lemma that the dense invariant holds, we show in Lemma [B(c,,rr) Σ غني E2 a lower bound for the number of points in Bic; 2r). Now, we charge all but at most ez Of to the points of Bic,, 2r) and mark these points as charged. We call this charging rule II. Note the difference between charging argument in Case and 2. In Case 1, we charge the points in O to themselves, but in Case 2, we charge them to points covered by B(c,, 2r). Recall that B(c,, 2r) and Of are disjoint.
3.9 that
K-1-1 at' In this way, we find an upper bound for the number of points in O and
ar points of
Observe that points in balls O'+1..... .% will not be charged to points in B(c, 2r). Indeed, points in balls O'41,'.. .Or are charged to the balls that our algorithms find either using rule I or rule II. However, this will not happen based on rule since B(c, 2r) is disjoint from all balls Of41,''.. .y. Moreover, rule II cannot also be applied since among balls O O+t1.-.. Oj, we already charged the points in O to B(c,, 2r) and points in "',,,-.., Og will be charged to points in balls ((c,+1. 2r).... ,B(c,,21) 2r).
Next, we consider how we update O2,0,,... Og. credits points. First, the variable of = [B(c,, 4r) U...UUUU O that corresponds to the number of points covered by B(c,, 4r) that are not covered by Of U02 U... U Oz- There are 2 -10 points from B(c,, 4r) that are free (i.e., no point charged to) and can still be charged. We consider these points as credits that we save and may use for future charging purposes.
Similar to case 1, we define the size of two sets of
There may also be previous modified balls Oj. with < that were considered in case 2 and still present in P;. More specifically, let z be the set of (there may exist) points in O2 n B(ey, 4r) that have been charged to distinct points in B(c,, 4r). For example, points a, b, c in case of be the number of such points. Since no points are charged to points in Zz" we save them as credit points for future charging purposes. We now update Oj, Oz.... ... Oj as follows: Of, Oz...... O2 stays the same and we define (2f - 101) + 2 artificial outliers in (0%+) U U....O,, n P.+1.
Figure 2 Let 2 = |
Now, for both cases, we apply charging rule to any points in the remaining modified balls 0 U...U O% that are inside B(c, 4r), These points are then marked as covered. See Figure 3 for an example. Note that these points will not be in Pi+1 = P. B(c, 4r). We assumed that O U UO2 U... U On covers all but at most points. After the charging has taken place and the modified clustering OGUOSU. Soo/U...UO,, .UO%, has been constructed, we have that 10' UO, = n E, in case (eg
254) -5 in case (25 10 + =z)).
Note that 10r] refers to the number of points covered by the modified ball Oj at the time of iteration
Then, by the way have charged O ... U O'2 our solution B(cr, 4r) U ..... U B(ck, 4r), we
obtain [B(c,, 4r) U...UU.. ..... U B(cr, 4r) 2 |0 U U... UO s + E3 in case (2f + =z))
+ ES in case 2 10 + =5)) = n (1 + 9) This concludes the proof of Part @ of the lemma. It
follows easily that when ToPr 5 r < (1 + T)rPP Part @ also holds, which completes the proof of this lemma.
Lemma 3.8. Let i be an iteration of the charging argument above such that we are in case 2. This means that ([c,, 2r) U... .. B(c,, 2r) does not intersect any of the remaining modified balls. Then, there must be remaining modified ball covering Σ ui-2
k-141 points.
For the proof of Lemma 3.8 see Supplementary Section

---

Lemma 3,9 (Coverage of ((q, 2r)), When we are in case of the charging argument for some iteration i, we nust have that [B 2r)
k-++1 ok
For the proof of Lemma 3.9 see Supplementary Section
3.3 Duration of dense clusters
After running Procedure 5 as subroutine, we know that each cluster C₁ covers at least points. More specifically, for each level i, if 2++1+ i(k-i41)-
14=2 then [B(,,, 2r) Z 2(k-i+1)
n:=2 and if 1ff++>>> n2-2
a(k-r+1)'
then [B(c,, 2r) 2 n--z two constraints, it will be dense for significant number of arbitrary operations. This will lead to the amortized update time being independent of n. The remaining lemmas are split into two cases,
cz
The following two lemmas show that when C₁ satisfies one of these
I-++I 3%
corresponding to the two cases in Procedure
Lemma 3.10 (Duration of dense cluster for is small). Assume that are currently at time t. ni-
Let us consider a level which = + S 3(k-i+1)' Let p = -rg mazpes, |Bp, (p', 2r)), and ni-2 Buax Br, (p. 2r). Assume that 2(k- S |Bmacl Then, we can add Br, (p, 4r) cluster in our solution, and this cluster will be dense until time t' = + t", with t" 2 1(K-111)
For the proof of Lemma 3.10 see Supplementary Section D
Lemma 3.11 (Duration of dense cluster for is large). Assume that are currently at time t. Let ni-=
2 + 1
1[k-1-1] for some level i. Let = arg maxyes, BBp, (p', and Bmax = Bp, (r,2r). S /Bax. Then,
Assune that -i-2 this cluster will be dense until time t' 1", with - (
add Bp, (p, 4r) cluster in solution, and
k-i+1
For the proof of Lemma 3.11 see Supplementary Section
3.4 Small radius guesses
It has not yet been considered what will happen if Procedure fails some level i. That is, when there exists no p E St such that Br, (p, 2r) covers sufficiently many points. Lemmas E. and E.2 show that if Procedure 5 fails at some level, then with high probability the guess of the optimal radius for that specific instance is too small (r < roPT). In this case, we postpone the construction of that level to time t + t*, referred to t, in the algorithm.
3.5 Computing update time
Finally, we prove the update time of algorithm. Lemma 3.4 Lemma 3.5 and Lemma 3.6 prove that the algorithms maintain the invariants with high probability. Together with Lemma 3.7 and Lemma F.1 this implies Theorem I.I
3.6 Robustness to adversarial inputs
Our dynamic algorithm is robust against an adaptive adversary. Specifically, we do not assume that the adversary has predetermined the sequence of updates in advance, with oblivious adversary. Instead, the adversary can query the insertion and deletion updates in an online manner, with knowledge of our solution.
We only use randomization to generate the sample set S; Procedure 5 which is then used to construct the levels. This randomness affects only the probability of failure in this procedure. After insertion or deletion updates, we not need to reconstruct level until it no longer satisfies the invariants. The guarantees we provide for how long level can remain valid are all in the worst case: therefore, they hold even when an adaptive adversary chooses the insertion and deletion operations online.
10

---

3.7 Acknowledgements
The authors would like to thank the anonymous reviewers for their insightful comments. Annika Hennes' and Melanie Schmidt's research was funded by the Deutsche Forschungsgemeinschat (DFG, German Research Foundation) project number 456558332.
References
[1] KohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Ra- jesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In Proceedings of the 2023 Anmual ACM-SIAN Sym- posium on Discrete Algorithms (SODA), pages 2677-2727. Society for Industrial and Applied Mathematics, 2023.
[2] Leyla Biabani, Annika Hennes, Morteza Monemizadeh, and Melanie Schmidt. Faster query times for fully dynamic k-center clustering with outliers. Advances in Neural Information Processing Systems, 36, 2024.
[3] Matteo Ceccarello, Andrea Pietracaprina, and Geppino Pucci. Solving k-center clustering (with outliers) in mapreduce and streaming, almost as accurately as sequentially. Proc. VLDB Endow., 12(7):766-77,, 2019.
[4] Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform center problem. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 55 LIPlcs. Leibniz Int. Proc. Inform., pages Art. No. 67, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016.
[5] T-H Hubert Chan, Silvio Lattanzi, Mauro Sozio, and Bo Wang. Fully dynamic k-center clustering with outliers. Algorithmica, 86(1):171-193, 2024.
[6] TH Hubert Chan, Amaud Guerqin, and Mauro Sozio. Fully dynamic k-center clustering. In Proceedings of the 2018 World Wide Web Conference, pages 579-587, Lyon, France, 2018. International World Wide Web Conferences Steering Committee.
[7] Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. pages 026-635, 1997.
[8] Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In S. Rao Kosaraju, editor, Proceedings of the Twelfth Annual Symposium Discrete Algorithms, January 7-9, 2001, Washington, DC, USA, pages 642-651. ACM/SIAM, 2001.
[9] Mark de Berg, Leyla Biabani, and Morteza Monemizadeh. k-center clustering with outliers in the MPC and streaming model. CoRR, 0bbs22302.128111 2023.
[10] Mark de Berg, Morteza Monemizadeh, and Yu Zhong. k-center clustering with outliers in the biding-windon model. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal ( (Virtual Conference), volume 204 of LIPlcs, pages 13:1-13:13 Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021.
[11] Hendrik Fichtenberger, Monika Henzinger, and Andreas Wiese. On fully dynamic constant- factor approximation algorithms for clustering problems. CoRR, abs/21 2021.
[12] Jinxiang Gan and Mordecai J Golin. Fully dynamic k-center in low dimensions via approximate furthest neighbors. 2024 Symposium on Simplicity Algorithms (SOSA), pages 269-278. SIAM, 2024.
[13] Teofilo Gonzalez. Clustering minimize the maximum intercluster distance. Theoretical computer science, 38:293-306, 1985.

---

[14] Gramoz Goranci, Monika Henzinger, Dariusz Leniowski, Christian Schulz, and Alexander Svozil. Fully dynamic k-center clustering in low dimensional metrics. In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), pages 143-153. SIAM, 2021.
[15] Dorit S Hochbaum and David B Shmoys. A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM (JACM). 33(3):533-550, 1986.
[16] Wen-Lian Hsu and George L Nemhauser. Easy and hard bottleneck location problems. Discrete Applied Mathematics, 1(3):209-215, 1979.
[17] Richard Matthew McCutchen and Samir Khuller. Streaming algorithms for k-center clustering with outliers and with anonymity. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 165-178. Springer, 2008.
[18) Paolo Pellizzoni, Andrea Pietracaprina, and Geppino Pucci. k-center clustering with outliers in sliding windows. Algorithms, 15(2):52, 2022.
[19] Paolo Pellizzoni, Andrea Pictracaprina, and Geppino Pucci. diversity maximization in doubling metrics. In Algorithms and Data Structures Symposium, pages 620-636. Springer, 2023.
Fully dynamic clustering and
[20] Melanie Schmidt and Christian Sohler. Fully dynamic hierarchical diameter k-clustering and k-center. arXiv preprini arXiv:/908.024 02645, 2019.
12

---

A Missing Pseudocode
In this section, we provide the missing pseudocodes. We start by Procedure INITIALIZZATON,, which is called to start the algorithm. This procedure defines the set R. and then creates a counter for time t, and the elements of our data structure Fr, Lr, and Z, that we discussed before. It also creates the variable i,,, which is used when the radius is smaller than TOPT. If < TOPT, may fail a level in Procedure OFFLINECLUSTER, and then have to stop
to find the p" that we desired the level construction. In this case, set t. to to t" to postpone the construction of that level to time + t* See Lemmas E.1 and E.2 for the choice of t". If tr is set to -1, means there is currently construction to be postponed. We assume all the parameters and variables defined in Procedure INIIIALIZATION are global, and the other procedures have access to them.
Then, we state Procedure UPDATE to handle the insertion or deletion of point p. Depending on whether the query is an insertion values of r. Then it updates the counter for time. Next, if there is any level construction that was postponed to the current time I, handles it.
deletion, it calls INSERT(p, r) or DELETE(P, r) for different
Procedure INITIALIZATION (k, 2, e, clmins dmax)
I: t 0
2: R: {[1 +e);; dmin S c) s (1 + e) i N}
3: for all r E R do
4: F, 0, C, t 2, 0
5:
t-- -1
6: end for
Procedure 2 UPDATE(P)
1: for all r E R do
2: if UPDATE(()) is an insertion then
3: INSERT
4: else if UPDATE(P) is deletion then
5: DELETE(P,
6: end if
7: end for
8: + i 1
9:
for all E R do
10: i', = then
11: X + JJ-
12:
OFFLINECLUSTER 1,r)
13: end if
14: end for
Procedure 3 (pSERT(p,T)
1: A [rl, (c1, .2.... Cx) F,,, and (C1, C2,..,, Cx} &- C,
2: if (Td(p.c) c;) < 4r for some E [X] then
3:
Ci+C, Up
4: else
5: Zr Zr Up
6: end if
7: For each level É, Pt (UegiSAC))
8: for i = to À do
9: if |C,] < min (
PP---
then
Ā-1+1
ak
10:
OFFLINECLUSTER(P...
break
12: end if
end for
13

---

Procedure 4 DELETE(P. r)
1:
X + F
2: pf 2, then
3:
remove p from 2,
4: else
5: Let C; be the cluster containing p. where E [V]
6:
P. < (UiSiSAC))) UZ, Z,
7:
if B(c, 2r) covers min [2+1, k-1+1 ab
Pp-= from P. then
8:
remove from C₁
9: else
10: OFLINECLUSTER(PP.rr))
end if
12:
end if
Procedure 5 OFFLINECLLUSTER(P.,,
1:
1r ---- -1
2: while
and P; + do 3: n4 +P,
4:
Pick uniform sample St of the 262 log points from P. I[M-++1) then
5:
if +15
6:
Find a point p" E S, such that [8p, (1p",2r)) 2 2(--+1))
7:
if there does not exist such p" then
8:
6 +++++ R 2[E-++2)
I/ See Lemma E.
break 10: end if
9:
11: else if x +
mi= [K-i+1] then
Find a point p" E S; such that [Br, (r))
2
m:-
there does not exist such a p" then k-1+1 3k
13:
14:
tfe + 28k
// See Lemma E.2
15:
break end if
16:
17: end if
18: c+pp p., C, + B(p", and P++1 + PrACs
iti+1
20:
end while
21:
F. 02 4-13, for (C1, C2, my C--13 Z, + P:
B Missing proofs Section 3.1
Lemma 3.4 (Procedure maintains invariants). Assume that time t, we have point set Pt. data assume that the level and dense invariants hold at time and r TPPT At the start time + we insert point p using Procedure 3 After the insertion, the level and dense invariunts still hold with probability 1 Procedure 5 was not called and with the where V > 1 Procedure 5 was not called.
structure DD,- (F,,,
probability of at least 2(k 2(k-i+1)
log
Proof. If we enter the case line the new point p will be added an existing cluster C,. Then, we have that Pj for all S and & P; for all > í. If we enter the case in line 4, the new point p added as an outlier. This is the highest level, so we have that p E P. for i. The level invariant is maintained by definition in these cases. If we enter the case in line 9 and recluster levels i,..., k. we recluster the points in P. as defined in line 7, and hence, none of the levels j < i are affected. Then by Lemma the level invariant is maintained for all levels. The dense invariant is maintained because of the check we do in line for levels. Furthermore, we choose the lowest level where the dense invariant does not hold and recluster from this level upwards. Hence, the
14

---

dense invariant will hold for all levels j < i. We call Procedure 5 on P,, so by Lemma 3.6 the dense invariant is maintained for levels j 2 i with probability 1 2(8-1-1) log with VP 2 1.
D
Lemma 3.5 (Procedure 4 maintains invariants), Assume that at time t, we have point set Pt, instance
D. = (Fr. Lr, 2,), parameters k. E N and > We assume that the level and dense invariants hold at time and r 2 TOPT- At the start of time + 1, we delete an arbitrary point p using Procedure 4 After the deletion, the level and dense invariants hold with probability 1 if Procedure
was not called, and with probability 1
2(k-i+1) with V if Procedure 5 was called. 2
Proof. If we enter the case in line 2, where p is an outlier, it follows easily that the level and dense invariants are maintained. In the second case, starting in line 4, p is in some cluster C, either as center as another point. If C2 still covers sufficiently many points after the deletion of p as described in line 7, it follows easily that the level invariant is maintained. For the dense invariant, note that for all levels j < i, n and with this - levels j > i, n2 remains unchanged. This observation, combined with the fact that for any + j. [C₁] is unchanged, means that the dense invariant still holds for all levels.
k-j+I at can only decrease. Furthermore, for all
If C₁ is no longer dense after deleting p. and we enter the case in line 9, the clusters in levels j < i remain unchanged. The level invariant will be maintained since Pj is updated P3 {p) for all j < i. The dense invariant is maintained in levels j < i by the same reasoning as the previous case. On the remaining points, Procedure 5 is called in line 10. Using Lemma (36] the level and dense invariants are maintained for the remaining levels with probability at least 2k-i+11 where V 2 1. Crucial for maintaining the level invariant is line 6. This line ensures that we do not consider the points in levels j < i when constructing level and any higher levels.
e lng
Lemma 3.6 (Procedure Sessedureemaaingg maintains invariants with high probability). Suppose the level and dense invariants hold for all levels < and we call Procedure Jo P. as the result of an insertion or deletion. Let X S k be random variable representing the number of levels we have after completing Procedure [ Ifr 2 TOPT. Procedure maintains the level and dense invariants for all levels j with
2(k-i+1) with V 2 1.
i i S À with probability at least e log
Proof. By the while-loop structure in combination with line 18, the level invariant is maintained for all levels j 2 i. For each newly constructed level j 2 i, there are cases within the while-loop.
For the first case where ++1 1 S na- JII we find a ball Bp, (y", 2r) that covers 2 with probability at least e if r 2 Torr. For the proof of this, we refer to Lemma E.
ni-z
points
-
Then, the dense invariant holds for any such level since
n 2(k - 4(k j + 1)
n
2 + min 2 + 1, nj 2
C2 k- +1 ak)
(I)
In the second case where x + 4( {(}- we find a ball Bp, (2",2r) that covers
n,-a
8k
points with probability 1 v 2 if r 2 TOPT- For the proof of this, we refer to Lemma E.2
Since 3 > a (see Section 2.4h. the dense invariant also holds for every level in this case. Then, the
probability that the dense invariant holds for all levels with < j S X is at least 1 2(R-++1)
This
lox
is because À - - k- - i is the number of new levels we constructed during Procedure 5
C Missing proofs Section 3.2
Lemma 3.8. Let i be an iteration of the charging argument above such that we are in case 2. This means that ((c,, 2r) U...U B(c,, 2r) does not intersect any of the remaining modified balls. Then, there must be a remaining modified ball covering I n,-2 k-i+1 points.
Proof. We prove this using strong induction on iterations in case 2. First, let consider the base case. In the base case, we are iteration which the first iteration to in case of the charging argument. There have been i iterations before i which were charged according to case 1. For any
15

---

O
B(c,22))
(r,
Figure 3: An example to illustrate the extra charging we do at the end of both cases I and 2. We are iteration i, and the ball B(q, 4r) covers two points from ball O/, with j The two points, shown in red, will be charged to themselves as in charging rule I and marked covered.
j < i, define z, to be the number of artificial outliers covered by B(e,, 4r). Then, for the remaining modified balls we have that:
i-1 = - Σ (of - 2z)))
i-1 Σ (cf Fz)) = m4
(2)
This is because assume that there are exactly z points outside our optimal solution O2 U...UUU O These 2 points are also outside Of U... O since for 1 S i S k. O2 S O₁ Of those 2 points, Ej z;y)) have not yet been seen in iteration. Hence, these points are definitely not covered by O U..... U. Furthermore, know that | xr)) artificial outliers have been defined in 0 U. U.,. in total. This is because all iterations < were in case I, and any artificial outliers present in O", will be propagated to (0)+1 U... ....UO)) n Pý+1, as these are included in zf. We subtract x; because these artificial outliers have already been counted by another 2f, and should not be counted again when computing the total amount of artificial outliers. Note that z iterations j < i as there were no previous iterations before j in case 2. Since at most πt; points are covered by O U?U... U there must be at least one of the modified optimal ball which covers < ni-a This concludes the proof of the base case. --++I
2j = 0 for all
Now, consider the inductive step. We are in iteration that in case 2. There have been previous iterations, of which an arbitrary number has been charged by case 2. Assume that for any such iteration j < i that was in case 2, we found an optimal ball O₂ that was covering at most ny - points. At the time of iteration j. the points of ball Oj were charged distinct points in B(cg. c 2r) but necessarily covered. In the iterations between and i, however, more points of the ball O may have been covered. Define On,unc as the points of O that are still uncovered the time of iteration i. Now, for the remaining modified balls, we should have that:
i-1
U U0 = =
(cf-21z) - j=1
Σ jei in case
(of + 25 xz))
Σ
(2f + 2/
10'1 -rry)
1 S
j<C caso
j<Z case
Similar to the base case, (2 Σj r,)) points will definitely be outside O'U... the iterations before < in case 1, (2 + 2/)) points are stored as credit. We subtract x, from this since we don't want recount outliers from previous iterations. In each iteration j < i that was in case 2, (zf + 2/ - 1) are stored as a credit. Even though B(cy, 2r) is disjoint from the remaining modified balls in this case, B(c,, 2r) can still cover some artificial outliers present in the remaining modified balls. We do not want to recount these for the total amount outliers in O U..... U./, and hence we subtract zj. Lastly, since the modified balls are disjoint, any points of O', with < and
iteration in case 2 that are still in the point set n, are not covered by O U.... U Oz We can rewrite
16

---

this as follows:
IO!U...UOO! = ni -
Σ f in case
+
E j-C in case 2
10/1=n= - -
(4)
This is because by the definition of =g. (E 2j Ejes in case 20 Since most n, points covered by Oj U...UO%. there must be at least of the remaining modified balls which covers n k-i+1
(.,ne)) =
- jist j case 2 Oo11
This concludes the proof.
Lemma 3,9 (Coverage of (c,, 2r)). When we are in case of the charging argument for some iteration i, we must have that [B(c, 2r)
- ak
E2
Proof. We prove the statement by induction on iterations i S case 2 of the charging argument. For the base case, iteration i is the first iteration in case 2. This means that for all previous iterations j < i, O has been charged and covered by charging rule Hence, B(c,, 2r) cannot intersect any such Oj since the points in Oj, are not in P.. We know that ((4,, 2r) also does not intersect any of the remaining modified balls by our assumption that iteration is in case Hence, (ic,, does not intersect Of UU..UUUU U. The ball B(c,, 2r) can cover S 2-j1 is the total number of artificial outliers present in U.U...U The ball ((c,, 2r) can cover at most (z -
1 (25 xÿ) artificial outliers, where x
xr2) other points, since there are exactly points outside O₁ U... U.O, of which Ef 2j) have been seen in previous ball 4r), for < Hence, [B(c,, 2r) S So, in order to satisfy the dense invariant, [B(c,, 2r) 2 Æ-++I ak
Now consider the induction case. We are in an arbitrary iteration in case 2. and there have been an arbitrary number of iterations < in case 2. For iterations < i in case 2, we assume that [B(e, 2r) 2 K-j+I
7,=2 - Even though B(e,, 2r) is disjoint from the remaining modified balls, it
can cover artificial outliers and
i-1 (2f .ry) other points. For x we have that:
x
Σ
(e) r,) +
Σ
+ x.))
(5)
jct case
JK1 in case
Ejein in (2f + 2 2z) are the total number of artificial outliers from iterations in case 1, and Ejen ene (25 + 2/ - 10'1 æz) are the total number of artificial outliers from case 2. Then, for the total amount points [cc,, 2r), we have:
[Bc, 2r) z
Σ
10' S
(6)
jdi
jei in case
This is because by the definition of 2 we have that Ejer 29 Ejein case 2O'). So, in order to satisfy the dense invariant, [B(c,,2r) 1-#41
n--2 #2 ak
This concludes the proof.
D Missing proofs Section 3.3
Lemma 3.10 (Duration of dense cluster for is small). Assume that we are currently at time t.
Let us consider a level which + S I(k-141) Let p org maz |Bp, (p', , 2r)), and ni=z S |Bmar). Then, we can add Br, (p, 4r) cluster in x/-s
ni-
Buax Bp, (p. 2r). Assume that 2(k-i+1) our solution, and this cluster will be dense until time L' = 1 + 1", with 1" 3(ー--11)
Proof. The subscript of n; will be omitted for simplicity. At time know that 2(k-1+1) |Bax]- The resulting cluster Bp, (p,45 4r) will be dense as long as Buax covers more than
min 2 1, p" ez points time L'. Hence, the dense invariant will not be broken as long as R-1F1 ak
17

---

Buax is greater than 2 + 1. Let t' be the time at which |max < 2 + 1. We can lower bound the time
t" between t and t' using the change in size of Bmxx. Then, we get the following lower bound:
2(k i -
Then, since 2 + 1 S n' by our assumption, we have: 1(6-1+1)
n² 2 n'
n²
(8)
2(k: - - 1) 4(k- - i+ 4(k - 16--i11 1)
This concludes the proof.
Lemma 3.11 (Duration of dense cluster for is large). Assume that we are currenily at time 1. Let n
level i. Let p arg / Es, [Br, (p', 2r)) and Bmax =Br, (p, 2r). S |Bmaxl- Then, we can add By, (p, 4r) as a cluster in our solution, and this cluster will be dense until time t' =t t", with t 52 )
2+1>
1(K for
Assume that k-1+1
c2
De
Proof. The subscript of n, will be omitted for simplicity. At time I, we know that K-1+1 I |maa The resulting cluster Bp, (p, 4r) will be dense long Baax covers more than n' min 12+1, 1, k-1+1 ax points at time '', with a a fixed constant smaller than B. Hence, the dense
invariant will not be broken as long Buix covers at least n"-
k-i#1 points. Let t' be the time
which maxx k-1+I at. We can lower bound by examining the change in size of Buax-
Using that n² n' t", we have:
n¹ - 2
EZ
71
EZ
2
1 i +
3k
-
k
i
ad
n'
n' +
62
E2
C2 e2
(9)
k - k-i+1 1
k - i+1
3k
ak
k: - i 1
3k
ak
Now, solving for 1" gives:
Ez(k - __
1
2k a 3 3
(10)
k(k-i+2)
3
Since and 3 are two fixed constants such that a, this gives t ())) This concludes the proof.
E Missing proofs Section 3.4
Lemma E.1 (Radius guess is small for z is small). Assume that we are currently at time t. Let us ni-2 consider level for which + +1 4[k-i+1j' Let p arg maxy'ss, BBp (r)), where S, the sample chosen in Algorithm
5 and Brax = Bp, 2r). Assume that |Bmaxl < -/-3
2(k-4+1)" Then, with
probability at least o for V 2 1, we have that r < TorT and until time = t t" we do not need to consider the instance for r, with t*
ni-s -42)
Proof. Let O .... Os be the optimal balls time Consider the same charging argument used in Lemma 3.7 where we charged one of the optimal balls to Bp, (cs, 4r) in each level i. Using Equation and the fact that O O, for each of the remaining optimal balls, we know that 10,U
O 2 n 2. Then, there must be at least one of the remaining optimal balls covering 2 1-++1 points. Let O the largest such ball. Using the Chernoff bound, we show that with high probability, one of the sampled points E S, O,. Define independent random variables X1,..., Xjo,I, one for each point in O, Each X,, corresponding point O,, will be if S,
18

---

and 0 otherwise. Define X =
Eja Xz.
We know that E[X,]
[8 11
Then, using linearity of
expectation, we find:
E | 10
[a
ni -4-2 2
Sill (ng - 2)
[:
2
(1
m
(11)
n2
nf.
k-i+1
n². k
k
The condition + - -i-
4[k-1+1] implies S
mi 4.
Then, since |S:| a/c 222 log
[1)++1)
follows that 1Sal (1 A 2 3 t/e - log Given that 1/ 2 63 and B a 2 1, this is at least
A log k 2 3 log & for 2 L.
Now, using the Chernoff bound, we find:
Pr||X- [
E[X] 2 E[X]] S 2e
FIXI
I
(12)
e log k
where V/ 2 1.
Hence, with probability of at least 1 -ioogz there will be at least point from O₂ in S, Let us call this point If 2 TOPT, Bp, (p, 2r) would cover all points of Og since p E O₂ and O has radius TOPT. However, since |Bmax| < -i==
2
1] we must have that r < TOPT.
Left to prove is that until time t' = t ++ we do not need this instance of r, where t* 2(k (+2)
ni-s To
this end, let m be Buax at time L. Consider the situation at time f. We know that max
2(6-
Let t' be some time after t such that | 2 xx
k-(+1' Hence, the instance for r becomes valid at time t'. We want derive a lower bound for t* t' t to complete the proof. By examining the change
in the size of B max. we derive the following lower bound:
nf 2
n
(13)
k iit1
2(k - + 1)
Using nf 2 nt - and subsequently solving for 1" we find that:
(14)
2(k - - 2)
This completes the proof.
Lemma E.2 (Radius guess is small for is large). Assume that we are currently at time t. Let us
consider level in which z 1+ I(k - 141) Let p- = arg maryes; (rr],, where S is the
sample chosen in Algorithm 5 and BLLx = Bp, (p. 2r). Assume that |Bmael <
24-2 cz
Then,
k-i41 Bkk
with probability at least -- i. for V 1, we have that < ToPT and until time t' = t. 1
do not need to consider the instance for r, with t 2 6s
29%
Proof. Let O1,..., be the optimal balls at time As in Lemma E.1 let O be the largest remaining optimal ball covering 2 -i-2 k-i+1 points. Using the Chernoff bound, we show that with high probability, one of the sampled points p S, is O, Define independent random variables X1,..., X X one for each point in O., Each Xy, corresponding to point E O₁, will be if E S:
and 0 otherwise. Define X expectation, we find
Σ j=
Xj.
We know that E[X,] = [8al n
Then, using linearity of
1.I1-10al
S
n
E[X]-
(15)
n
m
k -i+1
ni-z k-+41
Without loss of generality, we can assume
2 1. otherwise there would not need to be any points in the ball B3, (p, 2r) to satisfy the dense invariant, and level i would be trivial. Using this, Equation (15) can be simplified as follows:
MK
S
n
|S
62
E X
>
(16)
n
i
n2.
3k
19

---

We make case distinction. Either mi In this case, Equation (1) further simplifies to
c|S:
E Z
(17)
2,3
Recall that |Sp] Uie" k22 log k. Given that 2 6, and 3 > a 2 we have
E[X] 2 2
ub log k 2 3 log h: 2 3 log k
(18)
for some V 2 1. In the other case 2
n Equation
15) simplifies
S
n2/2
[S
1 2 De 'llogh 2 3 log
E
(19)
n k k-i+1
2k
2
for some V 2
In both cases, using the Chernoff bound, we find that with probability at least 1 - a r there will be at least one point from O, in X,. If 2 TOPT, Bp, (p, 2r) would cover all points of O2 since p O₂ and O₂ has radius TOPr. However, since |Buax] must have that TOPT-
ni-
nf i+1 I 10s],
k-1+1
Left to prove is that until time t' ++ with t- = -)))) we do not need this instance r.
r. To this
end, let B m be Bmax at time t. Consider the situation at time t. We know that [Btmaxl <
m| R- Bk
ts
Let t' be some time after t such that |8 2 ---+1- The cluster By, (p, 2r) in level is now covering sufficiently many points. We want to derive a lower bound for t = f. to complete the proof. By
examining the change in the size of Bmax and using that n 2 n t", we derive
n
1
(20)
1
--i+1
n 1* - 2
n1
62
(21)
1: -i+1
1: k-i+1
3k
-
62
+
(22)
k 4-ith ii11 1
Bk
as lower bound for t", Solving for t" gives
ea kk i + 1)
62
2
(23)
Bkik - i 2)
2,3
Since 3 is a constant, this is in (())) This concludes the proof.
F
Missing proofs from Section 3.5
Lemma F.1. The amortized update time of our dynamic algorithm is -3x0 (og() log( (A))
Proof. Let us fix an arbitrary time t and assume that at time 1, there are À S k clusters. Let time -'=l +++ 1" be the time at which we need to invoke Procedure on an arbitrary level i S k; due to the dense invariant being violated. We have two cases:
2 ++15 ni x(k-+1)) For this case, Lemma 3.10 shows the following: If we find a cluster such ni-
that |Br, (G, 2r) > 2(k-i-1j time then this cluster will remain dense for t* update operations (either insert or delete).
ni-z
n -
2 2+1>
4(k 4 For this case, Lemma 3.11 proves that if we find a cluster such that
-- BK at time 1, then this cluster will remain dense for the next 8' > ( ()) time steps. Asymptotically, 1" 2( By substituting the lower bound
BB,, (c;, 2r) >
n ni=
of in this formula, obtain t" (((3))
20

---

Observe that in both cases, we have a worst-case guarantee for the number of time steps during which the cluster By, (c,, 2r) remains dense. This, in turn, allows us to achieve worst-case amortized update time, rather than the weaker notion of expected amortized update time. We analyze the update time of each case separately.
ni-a and suppose that we find a cluster such 4(k-i+1)
Let us start with the first case which is 2 + 1 that [Br, (c,, 2r)
-i-s at time We know that t" 2 a(k-i+1j' The cost of reclustering levels i,..., according to Lemma 3.3 is O(n c- 1.3 log k), with nz S n t². Then, the amortized
-i-s
2[k-++1)
update time of arbitrary update operation is ( (m, + 10 log k) 0 2 1 log k).
Since: S T( [+1) we obtain 7 S n 4(k-++1)
nf
-i- I 4k -i- S 4k m1
mi
4k-
T 7[-+++)1- (k)) Thus, O 0 13 log k) = O log k).
40k 4(k-i+1)
Now, we consider the second case. Using a similar analysis as in the first case, we have t*
R ((()) Then, the amortized update time of an arbitrary update operation is O - log k)
Ole 2o k)..
After reclustering levels i..... kt there is no longer a lower bound for t" for levels j < i. Thus, could happen that such level needs to be reclustered soon after time f', Since j < k, this leads to an extra factor l such that the final amortized cost is O(<-2k log k).
Finally, we need to consider the case that offline clustering fails for a level i. That is, we fail to find ball covering sufficiently many points in Procedure 5 If offline clustering fails on some level in case 1, meaning fail to find ball such that [5r, (c,, 2r) 2[k-141]: then Lemma R.1 proves that with probability 1 1 gtr(ing 4y, the guess is small (i.e., r < TOPT) and indeed, remains small and we do not need to consider this guess until time t' = t" where t" 2 2(K-1+2)
zi-z
At time I', we recluster levels i,...,k. Then, since we are in the first case, we have = S of
T[--+1 Thus, the amortized update time of an arbitrary update operation in this case is (n +t)+ log k) = o log k) = O(e A log k) using Lemma 3.3
Next, we consider the situation when the offline clustering fails in case 2. Specifically, this occurs when we fail to find ball such that [By, (c. 2r) 2 k-++ ez According to Lemma E.2 the guess r is small (i.e., r < TOPT) with probability not need to consider this guess until time 1' = + t* where t' = ()()). This leads to an amortized update time of (c log k). As mentioned above, the running time needs to be multiplied by an additional factor to account for the possible need to recluster lower levels.
 and indeed, remains small and we do
guesses for the optimal radii. For small this is in O log A Thus, we derive the final amortized update time of ( log k log A).
Finally, we need to consider O (11 A
[og
G How to support discrete k-center clustering with outliers
Lemma G.1. Let (M,d) d) be a metric space and e > be an accuracy parameter. The spread ratio amma of all points ever inserted is assumed to be bounded. There exists a randomized fully dentes
dynamic algorithm that maintains a discrete k-center solution that allows up to (1 + <)2 many outliers on the current set of points. At every point in time I, the current clustering with centers c....., ex is a (4 + e) -approximation to an optimal solution for the (k, z)-center problem with high probability and e; E pt for all S X. Upon insertion or deletion of a point, the data structure updated in amortized update time O -36 log(k) lo)(
Proof. Let r and i be fixed, and e; be the center of cluster C, = Bp, (ca, 4r). As long as e; is not deleted, we report as the i-th center. Note that any feasible solution for the discrete version is also a feasible solution for the non-discrete version. Therefore, the optimal radius for the discrete version is not smaller than the optimal radius for the non-discrete version.
21

---

After the deletion of the point C₁2 we consider two cases: min R R-i+1 ok
or
then ni < (1 + 8)2 as and ni-2 The dense invariant states that [3,, (c,, 2r)] 2 min( k-1+1
Ez Ri-2 R-1+1 ok min +
> If min (= 1, k-++1 ak
1. Hence,
report all the n; points outliers and stop. We next consider the second case.
ak)- Therefore, [Bp, (q, 2r) > holds in the second case, and there exists a point E Bp, (q, 2r). Then we report an arbitrary point I E Bp, (c,, 2r) after the delction of q. Note that we do not replace с by ý in our data structure, and does not change in our data structure as long as the i-th level is not reconstructed. The point p is just the center that we report for the discrete version.
We next prove the 6-approximation guarantee. To do this, we show that C, S Big, 6r). This implies that any feasible solution with radius 4r for the non- don-discrete version can be used to report feasible solution for the discrete version. Also, see Figure 4 for a visual representation. Let g E C. We show that q Biβ, Gr). Since q E C. B(c; 4r), we have d(g, ci) S 4r. Moreover, d(c;; 2r since p E B(G, 2r). Then by the triangle inequality, we have
d(g. < d(g. c;) + d(cs.)) S 4r + 2r = 6r.
To report solution for the discrete version, is enough to keep Bic, 2r) n P.. Note that our data structure already stores C2 n P., and since Bec,, 2r) n P, S C2 n P. the space complexity and time complexity remain the same.
4r
4r
2r
2r
6r
C₁
Brc)
B(a, 2r)
C, = B(c,(, 4r)
C B(G, 4r)
B 6r)
Figure 4: Mustration of the claim's proof. Part (i): before deletion of G, we report e; as the center. Part (ii): after deletion of c, we report an arbitrary point ò E B(c;, 2r) as the center. Then, B(ù, Gr) can cover all the points in the cluster C..
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The problem setting stated at the beginning of the abstract summarizes this
paper's scope as formalized in Section 1.3 The main statements made in the abstract can be
found in Theorem 1.1 Section 1.I which is summarization of Lemma 3.7 in Section 3.2
and Lemma F. in Section 3.5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: As stated the abstract, Section Section 1.3 and the result Lemma 3.7 our algorithm yields a bicriteria approximation. This means that we approximate the objective function and also allow a slight violation of the outlier side constraint while comparing with an optimal solution that fulfills the side constraint exactly. Our results hold with high probability, which stated formally statement Lemma 3.6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "LLimitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
23

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
The problem setting alongside assumptions are stated in Section 1.3 This
paper's main statements Lemma 3.7 and Lemma [.I Lemma 3.8 and Lemma 3.9
are used to prove Lemma 3..7 It uses the assumption that the level and dense invariants
hold. Lemmaa(.6) Lemma 3.4 and Lemma 3.5 show that rumning our procedures maintains
these invariants. Lemma F.1 uses Lemma 3.3 Lemma 3.11 Lemma 3.10 Lemma E.
Lemma F.2
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
24

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not contain experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (lttps://nips.cc.
catssiionoollyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. https/ccppbcccgguuiddooooo /oodeSum/m asiionooicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification:
The paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
25

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///wwnrpppscccupculeeeeeeee
Answer: [Yes]
Justification: As our paper is of theoretical nature, most of the points addressed in the Code of Ethics do not apply. Further, we could not identify any foreseeable dangers or harms directly caused by the utilization of our results.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no foresccable direct societal impact of the work performed.
26

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
27

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, pwtpess.pppppsiteeepee thcode www.coo////aaa com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
28

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "vARY7fgvOz", "reviewer": "Reviewer_fRgM", "summary": "The paper gives a new algorithm for the dynamic version of k-center clustering with outliers. The algorithm works in the fully dynamic model with both point insertions and deletions allowed. The points can belong to an arbitrary metric space, compared to some previous algorithms addressing low-dimensional metric spaces.", "questions": "Is there a good reason why the algorithm is randomized? What are the obstacles to obtaining deterministic algorithms in this model?\n\nThe factor of $k^6$ in your upper bound is large. Is there a reason why in practice the algorithm would be significantly less costly?", "limitations": "No specific societal limitations to address. This is a theoretical work concerning a traditional computational problem.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "This is an important problem and the paper significantly improves the approximation factor.", "weaknesses": "The algorithm is randomized and works only against oblivious adversaries. This is a shared characteristic with the previous paper on this topic.\n\nThe algorithm achieves a better approximation factor than the previous algorithms, but it comes at the cost of significantly higher dependency in the update time on the number of clusters, k. In particular, the factor of $k^6$ is probably prohibitive in practice.\n\nOverall, even though this is a solid contribution to the study of the problem, this is not a breakthrough.\n\nI also wish the authors did a better job highlighting the technical ideas that lead to the improvement over the previous algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:** The algorithm is randomized and works only against oblivious adversaries. This is a shared characteristic with the previous paper on this topic.\n\n**Question:** Is there a good reason why the algorithm is randomized? What are the obstacles to obtaining deterministic algorithms in this model?\n\n**Response:** We address these two points together in our response. Interestingly, we have discovered that our dynamic algorithm not only can handle oblivious adversaries but is even adversarially robust. A dynamic algorithm is called adversarially robust if its performance guarantees (including the approximation factor and update time) are preserved even when the sequence of updates (i.e., insertions and deletions) is adaptively chosen by an adversary who observes the outputs of our algorithm throughout the sequence and adjusts them accordingly. An adversarially robust dynamic algorithm is more powerful than one designed to handle only an oblivious adversary, as an oblivious adversary cannot access the algorithm's outputs after each update. In particular, we only use random bits to sample from large clusters at each level and maintain a solution. (This is the only component of our algorithm that uses randomness.) The adversary, however, can observe the maintained solution after each update and adaptively modify future updates (insertions and deletions) accordingly. In contrast, the dynamic $14$-approximation algorithm developed by Chan et al. is designed only for oblivious adversaries and is therefore not adversarially robust. In particular, if their solution were revealed at any time, the adversary could impose costly update time  $\\Omega(n)$. \n\n**Question:** The factor of $k^6$ in your upper bound is large. Is there a reason why in practice the algorithm would be significantly less costly?\n\n**Response:** Thank you for raising this interesting question. The worst case occurs when the gap between the size of the ball chosen in the offline algorithm and the threshold is negligible, but we believe this is not always the case in practice. To increase this gap, we propose selecting the ball of maximum size in Line 8 of the OfflineCluster procedure. This adjustment does not change the theoretical bounds but can make the algorithm faster in practice.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dEzNRjebn4", "reviewer": "Reviewer_NQy9", "summary": "This paper studies the fully-dynamic $k$-center with outliers problem in the metric space. In this setting, operations (including insertion and deletion) appear over time. The performance evaluation of an algorithm is based on its cost approximation and the (amortized) update time. However, previous research has shown that when exactly excluding $z$ outliers is required, any $O(1)$-approximation algorithm incurs an $\\Omega(z)$ update time. It is therefore reasonable to allow for a trade-off by permitting $(1+\\varepsilon)z$ outliers in order to achieve efficient update times. \n\nThe proposed algorithm can be summarized as follows: It partitions the dataset into into at most $k+1$ levels, where each level $i$ represents a cluster $C_i$ with center $c_i$. The algorithm dynamically maintains a data structure that adapts to the operations performed in real-time. At every time, the data structure should maintain the following two invariants:\n\n- level invariant: Each level $i$ has a cluster $C_i$ such that $P_{i+1} = P_i \\backslash C_i$.\n- dense invariant: For each center $c_i$ in $F_r$, $B(c_i, 2r)$ covers sufficient points in $P_i$.\n\nThe authors prove that it is a $(4+\\varepsilon)$-approximation algorithm with $O(\\varepsilon^{-2}k^6\\log k\\log \\Delta)$ expected amortized update time.", "questions": "- can this method be slightly modified to support the change of $k$ and $z$. Alternatively, is there any negative results on handling the dynamic $k$ and $z$.\n- iDoes the analysis of the algorithm include a specific space complexity?  Additionally, i am curious about the hardness of the fully-dynamic clustering with outliers. Can you provide the lower bounds of the space and the update time in the context of the fully-dynamic setting?", "limitations": "thoretical paper", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written and easy to follow.\n- The algorithm provides a $(4+\\varepsilon)$-approximation algorithm for the fully-dynamic $k$-center with $z$ outliers problem, which is an improvement over previous work.\n- The paper includes a thorough theoretical analysis, proving the approximation guarantee and update time of the algorithm.", "weaknesses": "- the update time complexity $O(\\varepsilon^{-2}k^6\\log k\\log \\Delta)$ is not competitive, particularly for large $k$.\n- The paper does not provide empirical results or practical evaluations of the algorithm, which could demonstrate its performance in real-world scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:** the update time complexity $O(\\varepsilon^{-2}k^6\\log{k}\\log{\\Delta})$ is not competitive, particularly for large $k$.\n\n**Response:** Our goal was to develop a dynamic algorithm with a low approximation guarantee and a simple, elegant data structure. We did not focus on optimizing the exponent of $k$ in our running time. An interesting aspect of our method is that it is **adversarially robust**, meaning it can handle an adversary who observes the computed solution after each update and adjusts the subsequent updates accordingly. In contrast, the dynamic $14$-approximation algorithm developed by Chan et al. is not adversarially robust. If their solution is revealed at any time, the adversary can impose an expensive update that requires time in $\\Omega(n)$.\n\n**Comment:** The paper does not provide empirical results or practical evaluations of the algorithm, which could demonstrate its performance in real-world scenarios.\n\n**Response:** We agree with the reviewer that providing empirical results or practical evaluations would be valuable and interesting work. Our main focus was to improve the $14$-approximation guarantee and determine how much we could refine the approximation factor, leading to the development of the first adversarially robust dynamic $4$-approximation algorithm for the metric $k$-center problem with outliers. We consider conducting experiments and benchmarking our dynamic algorithm against the algorithm by Chan et al. for both real and synthetic scenarios as future work.\n\n**Question:** Can this method be slightly modified to support the change of $k$ and $z$. Alternatively, is there any negative results on handling the dynamic $k$ and $z$.\n\n**Response:** Our data structure is designed with up to $k$ levels, based on known values of $k$ and $z$. We are unsure how to modify our data structure to handle changes in $k$ and $z$ during the execution of the algorithm. Investigating the development of such a dynamic algorithm would indeed be an interesting challenge.\n\n**Question:** Does the analysis of the algorithm include a specific space complexity? Additionally, i am curious about the hardness of the fully-dynamic clustering with outliers. Can you provide the lower bounds of the space and the update time in the context of the fully-dynamic setting?\n\n**Response:** The space complexity of our algorithm is $O(\\epsilon^{-1}\\log(\\Delta)n)$. This is because we maintain $ \\epsilon^{-1} \\log(\\Delta) $ instances corresponding to different radius guesses, each containing up to $ n $ points. For the sample sets needed in $\\texttt{OfflineCluster}$, we also need $O(n)$ space because they form a subset of the dataset. Establishing a space lower bound for fully dynamic algorithms for $ k $-center with outliers would be an intriguing question.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L6QKk5meGm", "reviewer": "Reviewer_CFX4", "summary": "The paper studies the k-center clustering problem with outliers in the fully dynamic setting. Specifically, given a metric space (M,d), in the (k,z)-clustering problem, the goal is to find at most k balls minimizing the maximum ball radius while excluding up to z points from the clustering. In the fully dynamic setting, the points are inserted or deleted from the underlying metric space, and the goal is to maintain the clustering faster than recomputing from scratch after each insertion or deletion.\n\nThe main contribution of this paper is a fully-dynamic, provable approximation algorithm for the (k,z) clustering problem that achieves (4+\\eps)-approximation ratio, and can support point updates in O(\\eps^{-2} k^6 \\log k \\log \\Delta), with the caveat that the algorithm covers all but at most (1+\\eps)z points (also known as a bi-criteria guarantee in the approximation algorithms literature). The algorithm is randomized, and works against an oblivious, online adversary. It also improves upon the approximation ratio of (14+\\eps) achieved in the recent work Chan, Lattanzi, Sozio, and Wang [5] for the same problem, at the cost of increasing the running time by a factor of k^4.\n\nFrom a technical point of view, the paper first introduces a static (4+\\epsilon) approximation algorithm for the problem. The algorithm is itself based on the idea of successive random sampling, which proceeds as follows:\n\n*  guess an optimal radius r (this is standard in (clustering) algorithms, and can be achieved by binary searching at the cost of paying (1+\\eps) in the approx. factor, and a factor that is log of aspect ratio in the underlying metric space in the runtime);\n* pick uniformly at random a subset of points S of the current point set, and pick a center c from S that covers a good fraction of the current points; \n* grow a ball of radius 4r around the center c; \n* remove the points belonging to the ball from the current point sets, and continue with the next iteration (level)\n* the number of levels is bounded by roughly k\n* the centers computed in each level are output as the solution the (k,z) clustering problem\n\nThe bulk of the effort is then to carefully set up a data-structure that maintains these levels (and the associated information) under point insertion and deletions. There are two main invariants: (i) the level invariant and (ii) the dense invariant (which is roughly controlling the number of points that remain unclustered in each level). The moral message of the paper is that when the invariants are broken at some level i, then you basically re-cluster everything from that level up.", "questions": "Minor comments:\n\nLines 17-29, you should back up with citations the applications of clustering across many subfields of computer science and beyond\nLine 36, 'various complications' sounds a bit odd (maybe challenges would be a better fit here)\nLine 196, n_i, \\alpha never defined before in text\nLine 219, should your j start from 1 and not from i? -- similar comment for Definition 3.2\n\nMajor comment/question:\nLine 146 -- can you please elaborate whether non-discrete version of the (k,z) clustering you study here is less challenging? I imagine this helps you a lot with deletions; even if you delete a point in P, you can still leave the underlying point in M serve as cluster center, which doesn't invoke a re-build. Does the work of Chan et al. [5] have the some restriction?", "limitations": "Yes,", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "*The k-center clustering is a fundamental problem in the clustering/unsupervised learning literature. The outlier version of the problem makes perfect sense, and it's of equal importance. The dynamic setting is very natural and has received increasing attention in the clustering literature in the last 5 years or so, with many papers trying to nail down the dynamic complexity of basic clustering objectives such as k-center, k-median and k-means. This work can be thought as a continuation of this line of work. \n\n* The algorithm is simple and elegant (it should also be very implementable). Appropriate effort is put in explaining high level ideas. The paper reads well.", "weaknesses": "* Personally, I wouldn't agree that this is an improvement over the work of Chan et al. [5]. Indeed, it does achieve a better approximation ratio, but at the cost of increasing the runtime. The paper indeed provides a new, interesting trade-off, but I believe the abstract we should discuss this more carefully.\n\n* Regarding techniques, while one can argue that idea of successive sampling is now folklore, one influential work that employs a very similar algorithm is due to Mettu-Plaxton \"Optimal Time Bounds for Approximate Clustering\". While the original algorithm is for k-median and k-means, there are follow up works that employ the same algorithm for k-center (albeit with worst approx guarantee than 2). I would encourage the authors to discuss differences/similarities between Mett-Plaxton and their work. In my opinion, this doesn't diminish the contribution of the paper at hand.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:** Personally, I wouldn't agree that this is an improvement over the work of Chan et al. [5]. Indeed, it does achieve a better approximation ratio, but at the cost of increasing the runtime. The paper indeed provides a new, interesting trade-off, but I believe the abstract we should discuss this more carefully.\n\n**Response:** Thank you for the comment. We will discuss this trade-off in more detail in the full version. Besides the improvement in approximation factor, another interesting aspect of our method is that it is **adversarially robust**, meaning it can handle an adversary who observes the computed solution after each update and adjusts the subsequent updates accordingly. In contrast, the dynamic $14$-approximation algorithm developed by Chan et al. is **not** adversarially robust. In particular, if their solution is revealed at any time, the adversary can impose an expensive update that requires time in $\\Omega(n)$.\n\n\n**Comment:** Regarding techniques,[...] I would encourage the authors to discuss differences/similarities between Mett-Plaxton and their work. In my opinion, this doesn't diminish the contribution of the paper at hand.\n\n**Response:**  Thank you for highlighting the work of Mettu and Plaxton on 'Optimal Time Bounds for Approximate Clustering' and the subsequent research. We will be sure to discuss the differences and similarities between the work of Mettu and Plaxton and ours.\n\n**Question:** Lines 17-29, you should back up with citations the applications of clustering across many subfields of computer science and beyond \nLine 36, 'various complications' sounds a bit odd (maybe challenges would be a better fit here) \nLine 196, $n_i, \\alpha$ never defined before in text \nLine 219, should your j start from 1 and not from i? -- similar comment for Definition 3.2\n\n**Response:** Thank you for the valuable suggestions. We will make sure to add more references and the mentioned definitions at the correct positions in the full version.  \nThe subset $P_i$ of points not covered in level $i$ is disjoint from the clusters $C_1,\\ldots,C_{i-1}$. Hence, a clustering of $P_i$ does not need to contain these clusters. Similarly, a deletion of a point at level $i$ does not lead to a violation of the invariants in levels $1,\\ldots,i-1$, but can potentially violate the invariants at higher levels. Therefore, we only need to recluster the levels from $i$ upwards. We will make sure to write this part more clearly in the full version. \n\n**Question:** Major comment/question: Line 146 -- can you ,[...] Does the work of Chan et al. [5] have the some restriction?\n\n**Response:** We would like to thank you for bringing to our attention the interesting question about the discrete version of the problem we study in the paper. Indeed, we have thought about this question during the short rebuttal period and determined how our dynamic data structure can also provide a $6$-approximation solution for the discrete metric $k$-center problem with outliers, where centers must be selected from the input set of points. Observe that any feasible solution for the discrete version is also valid for the non-discrete version. Therefore, the optimal radius in the discrete version is at least as large as that in the non-discrete version. This suggests that, in certain applications, the non-discrete version may provide more precise clustering. We believe that both the discrete and non-discrete versions are valuable, each being particularly suited to different applications. Chan et al. [5] consider the discrete version; however, they need to reconstruct the leveling after the deletion of a center, making their algorithm not adversarially robust.\n\nHere, we prove how our data structure can also offer a $6$-approximation solution for the discrete version. We also attached a figure in the global rebuttal for a visual representation.\n\n**Claim**: Our data structure can report a $6$-approximation solution for the discrete version of the $k$-center problem with $z$ outliers without increasing the time or space complexity.\n\n**Proof:** Let $r$ and $i$ be fixed, and $c_i$ be the center of cluster $C_i=B(c_i,4r)$ (Recall that $B(x,\\rho)$ is the ball of radius $\\rho$ centered at $x$). To provide a solution for the discrete version, we do the following.\n\nAs long as $c_i$ is not deleted, we report $c_i$ as the $i$-th center. After the deletion of the point $c_i$, we consider two cases: $\\min(z+1,\\frac{n_i-z}{k-i+1}-\\frac{\\epsilon z}{\\alpha k})\\leq 0$ or $\\min(z+1,\\frac{n_i-z}{k-i+1}-\\frac{\\epsilon z}{\\alpha k})>0$. For the first case we have $n_i<(1+\\epsilon)z$ as $i\\geq 1$ and $\\alpha>1$. Hence, we can report all the $n_i$ points as outliers and stop. The dense invariant states that $|B(c_i,2r\\cap P_i|\\geq\\min(z+1,\\frac{n_i-z}{k-i+1}-\\frac{\\epsilon z}{\\alpha k})$. Therefore, $|B(c_i,2r)\\cap P_i|>0$ holds in the second case and there exists a point $\\hat{p}\\in B(c_i,2r)$. Then we report the point $\\hat{p}\\in B(c_i,2r)$ after the deletion of $c_i$.\n\nWe next prove the $6$-approximation guarantee. To do this, we show that $C_i\\subseteq B(\\hat{p},6r)$. This implies that any feasible solution in our data structure with radius $4r$ for the non-discrete version can be used to report a feasible solution for the discrete version. Also, see attached the figure in the global rebuttal for a visual representation. Let $q\\in C_i$. We show that $q\\in B(\\hat{p},6r)$. Since $q\\in C_i=B(c_i,4r)$, we have $d(q,c_i)\\leq 4r$ , where $d$ is the distance function. Moreover, $d(c_i \\hat{p}) \\leq 2r$ since $\\hat{p}\\in B(c_i,2r)$. Then by the triangle inequality we have $d(q, \\hat{p}) \\leq d(q,c_i)+d(c_i,\\hat{p})\\leq 4r+2r=6r.$\n\nThe complexity of space and time remains to be discussed. To report a solution for the discrete version, it is enough to keep $B(c_i,2r)\\cap P_i$. Note that our data structure already stores $C_i\\cap P_i$ , and since $B(c_i,2r)\\cap P_i \\subseteq C_i\\cap P_i$ , the space complexity and time complexity remain the same.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PdHW5dTgpd", "reviewer": "Reviewer_fWP4", "summary": "This paper proposes a simple but effective method that can solve \"fully dynamic k center problem with outliers\" in general metric space. The fully dynamic setting requires the algorithm to adjust its output efficiently when deletion or insertion operations  occur. This paper uses a \"ball cover\" strategy to obtain a $(4+\\epsilon)$-approximate solution of k center problem with outliers. The radii of balls will be guessed close enough to the optimal k center radius after at most $O(\\log \\Delta)$ iterations. When a deletion or insertion occurs, the algorithm needs to re-cluster (offline algorithm) if necessary. However, the paper proves that the re-clustering operation will not happen frequently. As a result, even though the time complexity of re-clustering may be as high as $O(n\\epsilon^{-1}k^3\\log k \\log \\Delta)$ in worst case, the amortized time can be reduced to $\\epsilon^{-2}k^6\\log k \\log \\Delta$ for handling the insertion or deletion of a single point.", "questions": "1. About the time complexity of binary search of $r_{OPT}$, you have mentioned that the set of all possible $r$ is $R = \\{(1+\\epsilon)^i:d_{min}\\le (1+\\epsilon)^i\\le d_{max}, i\\in N\\}$. So $|R| = \\log_{1+\\epsilon}\\Delta = \\frac{\\log \\Delta}{\\log (1+\\epsilon)}$. So if you binary search in the set $R$, it seems like that you only need $O(\\log |R|) = O(\\log \\log \\Delta)$ steps. So can your time complexity improved to $O(\\epsilon^{-2}k^6\\log k \\log \\log \\Delta)$?\n2. If I want to delete some point which is also a center of the solution. I think this center point should also be deleted since this point has been removed from this metric space. But it seems that Procedure 2 in the paper do not consider this situation. How do your algorithm handle the deletion of the center points?\n3. What is the size of your memory usage?", "limitations": "Please see weakness.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The approximate ratio of the proposed algorithm is $4+\\epsilon$, far better than previous paper like [5].\n2. The algorithm of this paper do not need extra assumption of metric space, *e.g.*, low doubling dimension assumption in [2], which makes the algorithm have strong applicability.\n3. The presentation is nice.", "weaknesses": "1. Time complexity. The amortized update time $\\epsilon^{-2}k^6\\log k \\log \\Delta$ is worse than the method in [5] (if $k$ is large), whose time complexity is $O(\\frac{k^2\\log \\Delta}{\\epsilon^2\\tau}\\log^2\\frac{1}{\\delta})$​.\n2. High update time complexity in the worst case. The proposed algorithm still need  $O(n\\epsilon^{-1}k^3\\log k \\log \\Delta)$  time to handle an insertion or deletion of a single point in the worst case.\n3. No experimental result. Although this work is mostly theoretical, it does not means that experiment is not necessary (especially for NeurIPS, not a purely theory venue). The previous work [5] provides the experimental results, so I strongly encourage the authors to compare the performance of both running time and cost to [5].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:** Time complexity. The amortized update time $\\epsilon^{-2}k^6\\log k\\log \\Delta$ is worse than the method in [5] (if $k$ is large), whose time complexity is $O(\\frac{k^2\\log\\Delta}{\\epsilon^2\\tau}\\log^2\\frac{1}{\\delta})$.\n\n**Comment:** High update time complexity in the worst case. The proposed algorithm still need $O(n\\epsilon^{-1}k^3\\log k\\log\\Delta)$ time to handle an insertion or deletion of a single point in the worst case.\n\n**Response:** Besides the improvement in approximation factor with respect to the algorithm in [5], another interesting aspect of our method is that it is **adversarially robust**, meaning it can handle an adversary who observes the computed solution after each update and adjusts the subsequent updates accordingly. In contrast, the dynamic $14$-approximation algorithm developed by Chan et al. is **not** adversarially robust. In particular, if their solution is revealed at any time, the adversary can impose an expensive update that requires time in $\\Omega(n)$. \n\nRegarding the question about handling an insertion or deletion of a single point in the worst case with $O(n \\epsilon^{-1} k^3 \\log k \\log \\Delta)$ time, we believe this can be managed with some adjustments to our algorithm. Specifically, we propose running two parallel instances of our algorithm. In the first instance, we compute and output the solution, while the second instance divides the large operations of $O(n \\epsilon^{-1} k^3 \\log k \\log \\Delta)$ time into smaller chunks of size $\\text{poly}(\\epsilon^{-1}, k, \\log k, \\log \\Delta)$ and processes each chunk sequentially after an update. When the solution maintained by the first run becomes invalid—potentially after $\\Omega(n)$ updates—we switch to the second run, obtain the solution from there, and continue the process. It is important to note that when switching between runs, we obtain a new solution and maintain that updated solution.\n\n**Comment:** No experimental result. [...] I strongly encourage the authors to compare the performance of both running time and cost to [5].\n\n**Response:**  We agree with the reviewer that providing empirical results or practical evaluations would be valuable and interesting work. Our main focus was to improve the $14$-approximation guarantee and determine how much we could refine the approximation factor, leading to the development of the first adversarially robust dynamic $4$-approximation algorithm for the metric $k$-center problem with outliers. We consider conducting experiments and benchmarking our dynamic algorithm against the algorithm by Chan et al. for both real and synthetic scenarios as future work.\n\n**Question:** About the time complexity of binary search of $r_{OPT}$, you have mentioned that the set of all possible $r$ is $R=\\{(1+\\epsilon)^i\\colon d_{\\min} \\leq (1+\\epsilon)^i \\leq d_{\\max}, i\\in N\\}$. So $|R| = \\log_{1+\\epsilon}\\Delta = \\frac{\\log\\Delta}{\\log(1+\\epsilon)}$. So if you binary search the set $R$, it seems like you only need $O(\\log|R|) = O(\\log\\log\\Delta)$ steps. So can your time complexity improved to $O(\\epsilon^{-2}k^6\\log k\\log\\log\\Delta)$?\n\n**Response:** For each guess $r \\in R $, we run an instance of the algorithm for that specific $ r $. After each insertion or deletion, we update all these instances. As a result, the update time is affected by a factor of $ |R| = \\log_{1+\\epsilon} \\Delta = O(\\epsilon^{-1}\\log{\\Delta})$. We apologize for any confusion caused by the title of that paragraph and will revise it accordingly.\n\n**Question:** If I want to delete some point which is also a center of the solution. I think this center point should also be deleted since this point has been removed from this metric space. But it seems that Procedure 2 in the paper do not consider this situation. How do your algorithm handle the deletion of the center points?\n\n**Response:** As mentioned in the paper, we studied the non-discrete version of the problem, where centers can be any point in the metric space. Therefore, a center can be a deleted point. We would like to thank you for bringing to our attention the interesting question about the discrete version of the problem we study in the paper. Indeed, we have thought about this question during the short rebuttal period and have provide a proof that explains how our dynamic data structure can also provide a $6$-approximation solution for the discrete metric $k$-center problem with outliers, where centers must be selected from the input set of points. \nYou can find the proof of this claim in the response to reviewer CFX4. We also attached a figure in the global rebuttal for a visual representation. Note that any feasible solution for the discrete version is also feasible for the non-discrete version. Therefore, the optimal radius for the discrete version is at least as large as that for the non-discrete version. This implies that, for some applications, the non-discrete version can offer more precise clustering. We believe both the discrete and non-discrete versions are important, each being better suited for different applications. Besides the improvement in approximation factor, another interesting aspect of our method is that it is **adversarially robust**, meaning it can handle an adversary who observes the computed solution after each update and adjusts the subsequent updates accordingly. In contrast, the dynamic $14$-approximation algorithm developed by Chan et al. is **not** adversarially robust. In particular, if their solution is revealed at any time, the adversary can impose an expensive update that requires time in $\\Omega(n)$.\n\n**Question:** What is the size of your memory usage?\n\n**Response:** The space complexity of our algorithm is $O(\\epsilon^{-1}\\log(\\Delta)n) $. This is because we maintain $ \\epsilon^{-1} \\log(\\Delta) $ instances corresponding to different radius guesses, each containing up to $ n $ points. The space required to temporarily store the sample sets used in Algorithm $\\texttt{OfflineCluster}$ is in $O(n)$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you to the reviewers for their insightful comments and valuable feedback. We also appreciate the time they dedicated to reviewing our work.

Here, we also provide a file with a figure illustrating our responses to reviewers CFX4 and fWP4.

Meta-review: This paper gives new ratio-time trade-offs for k-center with outliers in a general metric space. The reviews are overall positive, and the main strength is the improved ratio (albeit the dependence on k in running time is slightly worse). The main weakness is that the paper does not seem to make significant progress in terms of techniques, and there is no experiment.

During the discussion, the authors claim their result also works against an adaptive adversary (which was not mentioned in the submitted version). This feature is important and could be a major strength of the paper. The authors should include the relevant claim/proof to the final version.
Decision: Accept (poster)