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_cc_2024_Conference
Published: 2024-05-14 18:52:58

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.

Main paper: 
 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 are 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 are essential for organizing biological data and identifying patterns in genetic sequences, protein structures, and gene expression profiles. Similarly, in anomaly 38th Conference on Neural Information Processing Systems (NeurIPS 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, clustering 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 is to find k 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 c 1 , . . . , c k such that the balls ∪ k i=1 B P (c i , r) cover the point set. The k-center problem can be 2-approximated, and this is the best possible approximation guarantee [13] . In the last decade, the focus has shifted to analyzing the problem under various complications that arise in applications.One line of research is to 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 a 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.e., 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 + z centers, but z 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 r and k centers c 1 , . . . , c k such that the balls ∪ k i=1 B P (c i , r) cover all but z points. Solving clustering problems in the presence of 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 realworld 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. [8] . 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 z 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-dependent volume arguments.We study the general metric setting. General metric spaces represent a 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 O(1)-approximation algorithm for k-center clustering excluding at most z outliers has an amortized update time of Ω(z) [5] . For real-world applications, the fraction of outliers of the data could be arbitrarily large. Therefore, we allow for (1 + ϵ)z outliers to be excluded to avoid the dependence on z of the update time.The only previous work in this setting is the algorithm by Chan et al. [5] , which returns a solution with at most (1 + ϵ)z outliers with probability at least 1 -δ, for 0 < δ ≤ 1 k and ϵ > 0. It works by maintaining a clustering with t := k • ⌈log 1+ϵ k δ ⌉ clusters of radius 2r and using this to derive a final clustering with k clusters and radius 14r. They maintain such a clustering for all r ∈ Γ := {(1 + τ ) i : d min ≤ (1 + τ ) i ≤ (1 + τ ) • d max , i ∈ N}, with d min and d max the minimum and maximum distances, respectively, between any two points ever inserted. It is then shown that there exists an instance r ∈ Γ that will approximate the optimal radius to within a factor (14 + τ ), while allowing for (1 + ϵ)z outliers, with probability at least 1 -δ. The amortized time per update is O(|Γ| • k 2 ϵ 2 log 2 1 δ ), with |Γ| = (log dmax dmin )/τ . The total memory requirement is O(|Γ| • |n|) where n is the number of points in the current set.We introduce a novel fully dynamic (4 + ϵ)-approximation algorithm designed to maintain a k-center clustering while allowing for at most (1 + ϵ)z outliers at any time in the sequence.The expected amortized update time is O(ϵ -3 k 6 log(k) log(∆)) per operation (insertion or deletion). This is independent of z 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, 2, 18] ).Our main technical contribution is a novel combination of the sampling-based level data structure by Chan et al. [5] and the original greedy strategy by Charikar et al. [8] that enables us to achieve a much improved approximation guarantee compared to [5] .Theorem 1.1. Let (M, d) be a metric space and ϵ > 0 be an accuracy parameter. The spread ratio ∆ = dmax dmin of all points ever inserted is assumed to be bounded. There exists a randomized fully dynamic algorithm that maintains a k-center solution that allows up to (1 + ϵ)z many outliers on the current set of points. At every point in time, the current clustering is a (4 + ϵ)-approximation to an optimal solution for the (k, z)-center problem with high probability. Upon insertion or deletion of a point, the data structure is updated in amortized update time O(ϵ -3 k 6 log(k) log(∆)).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 is 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 + ϵ)-approximation. 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 a center gets deleted but only when a cluster does not contain enough points anymore. The algorithm handling the reclustering is 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 z outliers as given by Charikar et al. [8] and works by charging points from chosen clusters to points in optimal clusters. We follow the same iterative charging method but extend their approach by maintaining a 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 at currently active points, we can achieve a 6-approximation. We formalize this in Lemma G.1.The k-center problem is very well understood; two 2-approximation algorithms for it are known [13, 15] and a matching lower bound is also known [16] . The k-center problem with outliers was first studied and 3-approximated in [8] . In 2016, [4] gave a 2-approximation for this problem, but the algorithm is rather complex and less amenable to practical implementation. Charikar et al. [7] developed an elegant algorithm to maintain an 8-approximation for the vanilla k-center problem in the streaming model. Streaming can be seen as a dynamic insertion-only model. McCutchen and Khuller [17] improved this algorithm to a (2 + ϵ)-approximation and also extended it to a (4 + ϵ)-approximation 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 + ϵ)-approximation, but the algorithm for the general metric case is only stated as a O(1)-approximation.The fully dynamic k-center problem without outliers in general metrics was studied by [1, 6, 11] , and the best-known result is a (2+ϵ)-approximation with an amortized update time of O(k polylog(n, ∆)) by Bateni et al. [1] . The same paper also shows that any algorithm that provably satisfies a non-trivial approximation guarantee needs Ω(nk) 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 outliers was also studied for metrics with bounded doubling dimension [14, 19, 12] and in Euclidean space [20] .In the preliminaries section, we provide an introduction to the (k, z)-center problem and discuss the dynamic model used in our paper.We study the k-center clustering problem with z outliers, formally defined as follows.Definition 1.2 ((k, z)-center clustering). Let P be a point set in a metric space (M, d) and let k, z ∈ N be two parameters. The goal is to compute a set C ⊆ M of size at most k, such that the maximum distance of all but at most z points to their nearest c ∈ C is minimized. That is, find C such that min Z⊆P ,|Z|≤z max x∈P \Z min c∈C d(x, c), with |C| ≤ k.We define d min and d max as the minimum and maximum distances, respectively, between any two points ever inserted. The ratio ∆ = dmax dmin is referred to as the spread ratio, and is assumed to be bounded. Let r OPT be the optimal radius for the (k, z)-center clustering problem of a point set P . We also define the ball B P (c, r) = {p ∈ P : d(c, p) ≤ r} to be the set of points in P that are within distance r from c. If P is clear from the context, we may drop P from the definition B P (c, r). For a non-negative integer m, we denote{1, • • • , m} by [m].In the version of the (k, z)-center clustering problem that we consider, we allow (1 + ϵ)z outliers instead of strictly z. Furthermore, we require centers of clusters to be in the metric space (M, d), but they need not be currently present in P . This is referred to as the non-discrete version of the problem. Lemma G.1 in the Appendix shows how our data structure can also support the discrete version of the problem and provides a 6-approximation solution for it.Fully dynamic model. We consider the (k, z)-center clustering problem in the fully dynamic model against an adaptive adversary. In this model, we start with an empty point set, P = ∅, and process a sequence of operations determined by the adversary. We assume the adversary does not know the random bits chosen by our algorithm; however, it can observe the algorithm's output and adapt its responses in real time (unlike an oblivious adversary, which fixes a sequence of operations in advance). Each operation can be either an insertion, where a point from the metric space (M, d) is 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 t represent the point set P after t operations. In other words, P t consists of all points in (M, d) that have been inserted but not deleted after t operations. 
algorithm: 
 To explain the main ideas of our algorithm, we start by describing an iterative offline algorithm, which gives a (4 + ϵ) approximation for the (k, z)-center clustering problem.Offline algorithm. We start with a point set P 1 = P , ϵ > 0 and parameters k, z, r ∈ N. Here, r is a fixed guess for the optimal radius. For each iteration i, we sample a set of S i ⊂ P i of |S i | = ψϵ -1 k 2 log k points with replacement, uniformly at random. Here, ψ ≥ 6β is a constant, where β > α ≥ 1 are constants. We find a point c i ∈ S, such that B(c i , 2r) covers at least ϕ points from P i , where ϕ is some threshold to be defined later. We then create a new cluster C i = B Pi (c i , 4r), let P i+1 = P i \C i , and continue to the next iteration. We stop once k clusters have been created or P i = ∅. Let λ be a random variable representing the number of iterations we complete, where λ can be at most k. After we have done λ iterations we have computed clusters C 1 , C 2 , ..., C λ with corresponding centers c 1 , c 2 , ..., c λ . The points that are not covered by the union of these clusters will be the set of outliers that our algorithm reports. If the set of outliers is at most (1 + ϵ)z points, we can report a solution for the (k, z)-center clustering problem. This offline algorithm will be used as a 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 in that section.Guesses for unknown r OPT . Since the optimal r is usually not known, we can run the algorithm for all r ∈ R = {(1 + ϵ) i :d min ≤ (1 + ϵ) i ≤ (1 + ϵ) • d max , i ∈ N}.We then choose the smallest r ∈ R such that all but at most (1 + ϵ)z points are covered. We will show that this gives a (4 + ϵ)-approximation. Leveling. We can visualize the output of this algorithm as (at most) λ + 1 levels, where the first λ ≤ k levels each represent a cluster, and the last level represents the outliers (See Figure 1 ). More precisely, level i represents cluster C i with center c i , which was created in the i th iteration. Note that the construction of level i only considers the points in P i , which does not include points in the lower levels {1, 2, ..., i -1}.The main idea for the fully dynamic algorithm is to maintain each level i for i ∈ [λ + 1] under an arbitrary number of insertions and deletions by updating the cluster C i when necessary. In the rest of the paper, we use subscript i to refer to the level and superscript t to refer to the time. For example, P t i refers to the points present in level i at time t, and r t OPT refers to the optimal radius at time t. If the level or time is clear from the context, these may be omitted. For instance, if we define a situation at time t ′ , we will not repeat the superscript t ′ on every term.We will construct a clustering C 1 , . . . , C λ of the current set of points P t that we store in the data structure D r introduced by [6] . If t is clear from the context, we will just write P for P t . As we do not know the current optimal radius, we will maintain one data structure D r for every choice of r ∈ R = {(1 + ϵ) i : d min ≤ (1 + ϵ) i ≤ d max , i ∈ N}. Every data structure consists of up to λ ≤ k cluster-levels, with each level i containing a cluster C i . In level i, we keep track of the set of the points P i currently not covered, i. e., P i = P \ j<i C j . Level λ + 1 contains the outliers, i.e., Z r = P \ ∪ i≤λ C i . We denote n i = |P i |. By B(p, r) we denote the ball with radius r centered at p, and B A (p, r) = B(p, r) ∩ A for A ⊆ P .Let α ≥ 1. The data structure D r consists of the following components:① A list F r = {c 1 , c 2 , ..., c λ } of λ ≤ k centers. ② A list L r = {C 1 , C 2 , ..., C λ } of clusters with C i = B Pi (c i , 4r). ③ A set Z r = P \ ∪ i∈[λ] C i of outliers such that for all i ∈ [λ] and x ∈ Z r , d(x, c i ) > 4r.Let α ≥ 1 be a constant. We have the following invariants for D r .① Level invariant: for all i, P i+1 = P i \C i , withC i = B Pi (c i , 4r). ② Dense invariant: for all c i ∈ F r , |B Pi (c i , 2r)| ≥ min z + 1, ni-z k-i+1 -ϵz αk .When a new point p is inserted at time t, Procedure 3 in the appendix is executed. As input, we have D r at time t, p ∈ (M, d), ϵ > 0 and z, k ∈ N. First, we check whether p is inside one of the existing clusters, in which case we can add p to such a cluster. Otherwise, we add p to Z r . Next, we check if the dense invariant is maintained after the insertion of the new point. Generally, the dense invariant can be broken in two ways:➊ If the insertion of a new point results in more than (1 + ϵ)z outliers, then Lemma 3.7 shows that the dense invariant is no longer valid at some level i. ➋ If the addition of a point p to a cluster C i causes the dense invariant to be violated at some lower level j < i, that occurs because n t+1 j = n t j + 1.If the dense invariant is broken for some level i, we recluster levels i, ..., λ with λ ≤ k by invoking Procedure 5 as a sub-routine. Observe that if there are multiple levels i where the dense invariant is broken, we choose the lowest one.For the deletion of a point p at time t, Procedure 4 in the appendix is executed. The input is D r at time t, p ∈ (M, d), ϵ > 0 and z, k ∈ N. First we check if p is an outlier, in which case we remove p from Z r . If p is either a center or a point in a cluster, we find cluster C i which contains p. If cluster C i = B(c i , 4r) contains at least min z + 1, |Pi|-z k-i+1 -ϵz αk points, we do not re-cluster and simply remove p from C i . Note that the underlying point set exists in the metric space (M, d). If the center c i of a cluster C i is deleted, provided that the dense invariant remains valid, we can continue to utilize c i as the center of cluster C i , given our knowledge that the point c i is located within the metric space (M, d). In Lemma G.1, we explain how we can still obtain a 6-approximation if centers have to come from the current point set.If |C i | < min z + 1, |Pi|-zk-i+1 -ϵz αk after the deletion of p, then it also follows that |B(c i , 2r)∩ P i | < min z + 1, |Pi|-z k-i+1 -ϵz αk , i.e., the dense invariant is violated on this level. In this case, we want to redistribute the points in P i such that the levels i, . . . , λ fulfill the dense invariant. Deletion of a point in level i does not violate the invariants at levels 1, . . . , i -1. We re-cluster the points in (∪ i≤j≤k C j ) ∪ Z r using Procedure 5. We finish by updating D r .The clustering sub-routine is the offline algorithm that was described at the beginning of Section 2. The pseudocode of this sub-routine is shown in Procedure 5. We use it to iteratively build the levels of data structure D r . Two cases are distinguished based on whether z is small or large compared to the number of points in level i. In line 4, ψ is a constant with ψ ≥ 6β, where β > α, and α is the constant used in the dense invariant. The threshold ϕ that was introduced in Section 2 is different depending on the size of z compared ton i . If z + 1 ≤ ni-z 4(k-i+1) , then ϕ = ni-z 2(k-i+1) and if z + 1 > ni-z 4(k-i+1) , then ϕ = ni-z k-i+1 -ϵz βk .If we find multiple points p * in line 6 or 12 we choose one arbitrarily.The first step will be to initialize all D r such that F r , L r , Z r = ∅. Then, the algorithm waits for an insertion or deletion operation. If a point is inserted, Procedure 3 is executed, and if a point is deleted, Procedure 4 is executed. The algorithm is ran simultaneously for all r ∈ R = {(1 + ϵ) i :d min ≤ (1 + ϵ) i ≤ (1 + ϵ) • d max , i ∈ N}.In the next sections, it will be shown that a (4 + ϵ)-approximation is given by the clustering L r with r ∈ R the smallest r for which |Z r | ≤ (1 + ϵ)z. 
analysis: 
 We begin our analysis of the dynamic algorithm by introducing the concept of a dense cluster and specifying the criteria for a valid solution.Definition 3.1 (Dense cluster). A cluster B Pi (c i , 4r) is dense with respect to point setP i if it satisfies the dense invariant. That is, |B Pi (c i , 2r)| ≥ min z + 1, ni-z k-i+1 -ϵz αk .Observe that for the dense invariant, we consider the ball B Pi (c i , 2r) with a radius of 2r. However, a cluster (as seen in line 18 of Procedure5) corresponds to the points within the ball B Pi (c i , 4r), which has a radius of 4r.Definition 3.2 (Valid solution). A solution B P1 (c i , 4r) ∪ • • • ∪ B P λ (c λ , 4r) with λ ≤ k for point set P 1 is valid if it covers all but at most (1 + ϵ)z points from P 1 . We refer to each cluster B Pj (c j , 4r) for j ∈ {i, . . . , λ} of a valid solution as a valid cluster. Proof. In each iteration of the while-loop, we need to compute |B(p, 2r)| for all p ∈ S i . Since|S i | = O(ϵ -1 k 2 log k), this takes O(nϵ -1 k 2 log k) time.There can be at most k iterations of the while-loop and hence the total running time is O(nϵ -1 k 3 log k).In Supplementary Section B, we prove the following three lemmas. Lemmas 3.4 and 3.5 show that 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 5 as a subroutine upon the insertion or deletion of an arbitrary point with high probability if r ≥ r OPT . The case where r < r OPT is considered in Lemmas E.1 and E.2. Lemma 3.4 (Procedure 3 maintains invariants). Assume that at time t, we have point set P t , data structure D r = (F r , L r , Z r ). We assume that the level and dense invariants hold at time t and r ≥ r t+1 OPT . 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 1 -2(k-i+1) e Ψ log k , where Ψ ≥ 1 if Procedure 5 was not called. Lemma 3.5 (Procedure 4 maintains invariants). Assume that at time t, we have point set P t , instance D r = (F r , L r , Z r ), parameters k, z ∈ N and ϵ > 0. We assume that the level and dense invariants hold at time t and r ≥ r t+1OPT . At the start of time t + 1, we delete an arbitrary point p using Procedure 4. After the deletion, the level and dense invariants hold with probability 1 if Procedure 5 was not called, and with probability 1 -2(k-i+1) e Ψ log k with Ψ ≥ 1 if Procedure 5 was called. Lemma 3.6 (Procedure 5 maintains invariants with high probability). Suppose the level and dense invariants hold for all levels j < i and we call Procedure 5 on P i as the result of an insertion or deletion. Let λ ≤ k be a random variable representing the number of levels we have after completing Procedure 5. If r ≥ r OPT , Procedure 5 maintains the level and dense invariants for all levels j with i ≤ j ≤ λ with probability at least 1 -2(k-i+1) e Ψ log k , with Ψ ≥ 1.Next, we prove that if the invariants hold, our data structure D r = (F r , L r , Z r ) contains a valid solution to the k-center with z outliers problem. Furthermore, if r < (1 + ϵ)r OPT , D r provides a (4 + ϵ)-approximation. Without loss of generality, for simplicity we assume that D r 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 ≤ k. Then we have the following guarantees:① Valid solution: If r OPT ≤ r, then B(c 1 , 4r) ∪ . . . ∪ B(c k , 4r) covers all but at most (1 + ϵ α )z outliers in P . ② Approximate solution: If r OPT ≤ r < (1 + ϵ)r OPT , then B(c 1 , 4r) ∪ . . . ∪ B(c k , 4r) gives a(4 + ϵ)-approximation for the k-center with z outliers problem on P .Proof. Recall that the level invariant states that for all i, we have P i+1 = P i \B(c i , 4r) and the dense invariant states that for all i, we have that |B(c i , 2r)∩ P i | ≥ min(z + 1, ni-z k-i+1 -ϵz αk ).Assume that in the optimal solution, we have balls O 1 , . . . , O k with radius ≤ r OPT . The union of these balls covers all but z points in P . In order to prove Part ①, we aim to charge all but at most ϵ α z points of the optimal solution to points in our solution B(c 1 , 4r) ∪ . . . ∪ B(c k , 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 our solution to charge the points in the optimal balls. To this end, we construct modified optimal balls O ′ 1 , . . . , O ′ k , where O ′ i ⊆ O i for every i ≤ k. For the base case, we haveO ′ 1 = O 1 , • • • , O ′ k = O k .We will show that we can order the modified balls in such a way, that at the end of time step i, all but at most ϵz αk • i points from the first i modified balls are charged to distinct points in B(c 1 , 4r) ∪ . . . ∪ B(c i , 4r). This will allow us to prove that our solution covers at least as many points as the optimal solution.Assume that all but at most ϵz αk We maintain two sets of credit points that we save and may use for future charging purposes. First, the set• (i -1) points in the first i -1 modified balls O ′ 1 ∪ O ′ 2 ∪ . . . ∪ O ′ i-1 have been charged to distinct points in B(c 1 , 4r) ∪ . . . ∪ B(c i-1 ,c i O i |O i | ≤ n2-z k-2+1 |B(c i , 2r)| ≥ n2-z k-2+1 -z αk 2r 4r a b c B(c i , 2r) B(c i , 4r) O i 2r rOP T 4r p q B(c i , 4r) (Case 1) (Case 2)Z c i = B(c i , 4r)\(O ′ 1 ∪ . . . ∪ O ′ k ) which is the set of points covered by B(c i , 4r) that are not covered by O ′ 1 ∪ O ′ 2 ∪ . . . ∪ O ′ k . We let z c i = |Z c i |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 c i , allowing us to use them later. We refer to these points as credit points.There may also be previous modified balls O ′ j , with j < i that were considered in case 2 and are still present in P i . More specifically, let Z d i be the set of (there may exist) points in O ′ j ∩ B(c j , 4r) that have been charged to distinct points in B(c j , 4r) (See the discussion of case 2, below). For example, points a, b, c in case 2 of Figure 2 i 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 O ′ i exists. Using the assumption of this lemma that the dense invariant holds, we show in Lemma 3.9 that|B(c i , 2r)| ≥ ni-z k-i+1 -ϵz αk .In this way, we find an upper bound for the number of points in O ′ i and a lower bound for the number of points in B(c i , 2r). Now, we charge all but at most ϵz αk points of O ′ i to the points of B(c i , 2r) and mark these points as charged. We call this charging rule II. Note the difference between charging argument in Case 1 and 2. In Case 1, we charge the points in O ′ i to themselves, but in Case 2, we charge them to points covered by B(c i , 2r). Recall that B(c i , 2r) andO ′ i are disjoint. Observe that points in balls O ′ i+1 , • • • , O ′ k will not be charged to points in B(c i , 2r). Indeed, points in balls O ′ i+1 , • • • , O ′k are charged to the balls that our algorithms find either using rule I or rule II. However, this will not happen based on rule I sinceB(c i , 2r) is disjoint from all balls O ′ i+1 , • • • , O ′ k .Moreover, rule II cannot also be applied since among ballsO ′ i , O ′ i+1 , • • • , O ′ k , we already charged the points in O ′ i to B(c i , 2r) and points in O ′ i+1 , • • • , O ′ k will be charged to points in balls B(c i+1 , 2r), • • • , B(c λ , 2r).O ′ 1 , O ′ 2 , . . . , O ′ k .Similar to case 1, we define the size of two sets of credits points. First, the variablez c i = |B(c i , 4r)\(O ′ 1 ∪ . . . ∪ O ′ k )| that corresponds to the number of points covered by B(c i , 4r) that are not covered by O ′ 1 ∪ O ′ 2 ∪ . . . ∪ O ′ k . There are z c i -|O ′ i | points from B(c i , 4r) that are free (i.e., no point is charged to) and can still be charged. We consider these points as credits that we save and may use for future charging purposes.There may also be previous modified balls O ′ j , with j < i that were considered in case 2 and are still present in P i . More specifically, let Z d i be the set of (there may exist) points in O ′ j ∩ B(c j , 4r) that have been charged to distinct points in B(c j , 4r). For example, points a, b, c in case 2 of Figure 2 k that are inside B(c i , 4r). These points are then marked as covered. See Figure 3 for an example. Note that these points will not be in P i+1 = P i \B(c i , 4r). We assumed that O 1 ∪ O 2 ∪ . . . ∪ O k covers all but at most z points. After the charging has taken place and the modified clusteringO ′ 1 ∪O ′ 2 ∪. . .∪O ′ k has been constructed, we have that |O ′ 1 ∪O ′ 2 ∪. . .∪O ′ k | = n-z -j in case 1 (z c j + z d j ) -j in case 2 (z c j -|O ′ j | + z d j ). Note that |O ′ j |refers to the number of points covered by the modified ball O ′ j at the time of iteration j. Then, by the way we have chargedO ′ 1 ∪ . . . ∪ O ′ k to our solution B(c 1 , 4r) ∪ . . . ∪ B(c k , 4r), we obtain |B(c 1 , 4r) ∪ . . . ∪ B(c k , 4r)| ≥ |O ′ 1 ∪ O ′ 2 ∪ . . . ∪ O ′ k | -ϵz α + j in case 1 (z c j + z d j ) + j in case 2 (z c j -|O ′ j | + z d j ) = n -(1 + ϵ α )z.This concludes the proof of Part ① of the lemma. It follows easily that when r OPT ≤ r < (1 + ϵ)r OPT , 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 B(c 1 , 2r) ∪ . . . ∪ B(c i , 2r) does not intersect any of the remaining modified balls. Then, there must be a remaining modified ball covering ≤ ni-z k-i+1 points.For the proof of Lemma 3.8, see Supplementary Section C.Lemma 3.9 (Coverage of B(c i , 2r)). When we are in case 2 of the charging argument for some iteration i, we must have that|B(c i , 2r)| ≥ ni-z k-i+1 -ϵz αk .For the proof of Lemma 3.9, see Supplementary Section C.After running Procedure 5 as a subroutine, we know that each cluster C i covers at least ϕ points. More specifically, for each level i,if z+1 ≤ ni-z 4(k-i+1) , then |B(c i , 2r)| ≥ ni-z 2(k-i+1) and if z+1 > ni-z 4(k-i+1) , then |B(c i , 2r)| ≥ ni-z k-i+1 -ϵz βk .The following two lemmas show that when C i satisfies one of these two constraints, it will be dense for a 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, corresponding to the two cases in Procedure 5.Lemma 3.10 (Duration of dense cluster for z is small). Assume that we are currently at time t. Let us consider a level i in which z + 1 ≤EQUATIONB max = B Pi (p, 2r). Assume that n t i -z 2(k-i+1) ≤ |B max |.Then, we can add B Pi (p, 4r) as a cluster in our solution, and this cluster will be dense until time t ′ = t + t * , with t * ≥n t i -z 4(k-i+1) .For the proof of Lemma 3.10, see Supplementary Section D.Lemma 3.11 (Duration of dense cluster for z is large). Assume that we are currently at time t. Let z + 1 >n t i -z 4(k-i+1) for some level i. Let p = arg max p ′ ∈Si |B Pi (p ′ , 2r)|, and B max = B Pi (p, 2r). Assume that n t i -z k-i+1 -ϵz βk ≤ |B max |.Then, we can add B Pi (p, 4r) as a cluster in our solution, and this cluster will be dense until time t ′ = t + t * , with t * = Ω( ϵz k ).For the proof of Lemma 3.11, see Supplementary Section D.It has not yet been considered what will happen if Procedure 5 fails on some level i. That is, when there exists no p ∈ S i such that B Pi (p, 2r) covers sufficiently many points. Lemmas E.1 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 < r OPT ). In this case, we postpone the construction of that level to a time t + t * , referred to as t ′ r in the algorithm.Finally, we prove the update time of our 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 1.1.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, as with an 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 i in Procedure 5, which is then used to construct the levels. This randomness affects only the probability of failure in this procedure. After the insertion or deletion updates, we do not need to reconstruct a level until it no longer satisfies the invariants. The guarantees we provide for how long a 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.In this section, we provide the missing pseudocodes. We start by Procedure INITIALIZATION, 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 F r , L r , and Z r that we discussed before. It also creates the variable t ′ r , which is used when the radius r is smaller than r OPT . If r < r OPT , we may fail to find the p * that we desired for a level i in Procedure OFFLINECLUSTER, and then have to stop the level construction. In this case, we set t ′ r to t + t * to postpone the construction of that level to time t + t * . See Lemmas E.1 and E.2 for the choice of t * . If t ′ r is set to -1, it means there is currently no construction to be postponed. We assume all the parameters and variables defined in Procedure INITIALIZATION are global, and the other procedures have access to them.Then, we state Procedure UPDATE to handle the insertion or deletion of a point p. Depending on whether the query is an insertion or a deletion, it calls INSERT(p, r) or DELETE(p, r) for different values of r. Then it updates the counter for time. Next, if there is any level construction that was postponed to the current time t, it handles it.Procedure 1 INITIALIZATION(k, z, ϵ, d min , d max ) 1: t ← 0 2: R := {(1 + ϵ) i : d min ≤ (1 + ϵ) i ≤ (1 + ϵ)d max , i ∈ N} 3: for all r ∈ R do 4: F r ← ∅, L r ← ∅, Z r ← ∅ 5:t ′ r ← -1 OFFLINECLUSTER(Z r , λ r + 1, r)13:end if 14: end for Procedure 3 INSERT(p, r) 1: λ ← |F r |, {c 1 , c 2 , ..., c λ } ← F r , and {C 1 , C 2 , ..., C λ } ← L r 2: if d(p, c i ) ≤ 4r for some i ∈ [λ] then 3: C i ← C i ∪ p 4: else 5: Z r ← Z r ∪ p 6: end if 7: For each level ℓ, P ℓ ← (∪ ℓ≤j≤λ C j ) ∪ Z r 8: for i = 1 to λ do 9: if |C i | ≤ min z + 1, |Pi|-z k-i+1 -ϵzP i ← (∪ i≤j≤λ C j ) ∪ Z r 7: if B(c i , 2r) covers > min z + 1, |Pi|-z k-i+1 -ϵzn i ← |P i | 4:Pick a uniform sample S i of ψϵ -1 k 2 log k points from P i 5:if z + 1 ≤ ni-z 4(k-i+1) then 6: Find a point p * ∈ S i such that |B Pi (p * , 2r)| ≥ ni-z 2(k-i+1) 7:if there does not exist such a p * then 8: i ← i + 1 20: end while 21: F r ← {c 1 , c 2 , ..., c i-1 }, L r ← {C 1 , C 2 , ..., C i-1 } , Z r ← P i B Missing proofs Section 3.1 Lemma 3.4 (Procedure 3 maintains invariants). Assume that at time t, we have point set P t , data structure D r = (F r , L r , Z r ). We assume that the level and dense invariants hold at time t and r ≥ r t+1t ′ r ← t + ni-z 2(k-i+2) // See LemmaOPT . 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 1 -2(k-i+1) e Ψ log k , where Ψ ≥ 1 if Procedure 5 was not called.Proof. If we enter the case in line 2, the new point p will be added to an existing cluster C i . Then, we have that p ∈ P j for all j ≤ i and p / ∈ P j for all j > i. If we enter the case in line 4, the new point p is added as an outlier. This is the highest level, so we have that p ∈ P i for all 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 i as defined in line 7, and hence, none of the levels j < i are affected. Then by Lemma 3.6, the level invariant is maintained for all levels. The dense invariant is maintained because of the check we do in line 9 for all levels. Furthermore, we choose the lowest level i where the dense invariant does not hold and recluster from this level upwards. Hence, the dense invariant will hold for all levels j < i. We call Procedure 5 on P i , so by Lemma 3.6, the dense invariant is maintained for levels j ≥ i with probability 1 -2(k-i+1) e Ψ log k , with Ψ ≥ 1.Lemma 3.5 (Procedure 4 maintains invariants). Assume that at time t, we have point set P t , instance D r = (F r , L r , Z r ), parameters k, z ∈ N and ϵ > 0. We assume that the level and dense invariants hold at time t and r ≥ r t+1 OPT . At the start of time t + 1, we delete an arbitrary point p using Procedure 4. After the deletion, the level and dense invariants hold with probability 1 if Procedure 5 was not called, and with probability 1 -2(k-i+1) e Ψ log k with Ψ ≥ 1 if Procedure 5 was called.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 i , either as a center or as another point. If C i 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 j and with this nj -z k-j+1 -ϵz αk can only decrease. Furthermore, for all levels j > i, n j remains unchanged. This observation, combined with the fact that for any i ̸ = j, |C j | is unchanged, means that the dense invariant still holds for all levels.If C i 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 P j is updated to P j \{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 3.6, the level and dense invariants are maintained for the remaining levels with probability at least 1 -2(k-i+1) e Ψ log k , where Ψ ≥ 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 i and any higher levels. Lemma 3.6 (Procedure 5 maintains invariants with high probability). Suppose the level and dense invariants hold for all levels j < i and we call Procedure 5 on P i as the result of an insertion or deletion. Let λ ≤ k be a random variable representing the number of levels we have after completing Procedure 5. If r ≥ r OPT , Procedure 5 maintains the level and dense invariants for all levels j with i ≤ j ≤ λ with probability at least 1 -2(k-i+1) e Ψ log k , with Ψ ≥ 1.Proof. By the while-loop structure in combination with line 18, the level invariant is maintained for all levels j ≥ i. For each newly constructed level j ≥ i, there are two cases within the while-loop.For the first case where z + 1 ≤ nj -z 4(k-j+1) , we find a ball B Pj (p * , 2r) that covers ≥ nj -z 2(k-j+1) points with probability at least 1 -2 e Ψ log k if r ≥ r OPT . For the proof of this, we refer to Lemma E.1. Then, the dense invariant holds for any such level sinceEQUATIONIn the second case where z + 1> nj -z 4(k-j+1) , we find a ball B Pj (p * , 2r) that covers ≥ nj -z k-j+1 -ϵz βk points with probability 1 -2 e Ψ log k if r ≥ r OPT .For the proof of this, we refer to Lemma E.2. Since β > α (see Section 2.4), the dense invariant also holds for every level in this case. Then, the probability that the dense invariant holds for all levels j with i ≤ j ≤ λ is at least 1 -2(k-i+1) e Ψ log k . This is because λ -i + 1 ≤ k -i + 1 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 B(c 1 , 2r) ∪ . . . ∪ B(c i , 2r) does not intersect any of the remaining modified balls. Then, there must be a remaining modified ball covering ≤ ni-z k-i+1 points.Proof. We prove this using strong induction on iterations in case 2. First, let us consider the base case. In the base case, we are in iteration i which is the first iteration to be in case 2 of the charging argument. There have been i -1 iterations before i which were charged according to case 1. For anyB(c i , 4r) O i O jB(c i , 2r) Figure 3 : An example to illustrate the extra charging we do at the end of both cases 1 and 2. We are in iteration i, and the ball B(c i , 4r) covers two points from ball O ′ j , with j > i. The two points, shown in red, will be charged to themselves as in charging rule I and marked as covered. j < i, define x j to be the number of artificial outliers covered by B(c j , 4r). Then, for the remaining modified balls we have that:EQUATIONThis is because we assume that there are exactly z points outside our optimal solution O 1 ∪ . . . ∪ O k . These z points are also outsideO ′ 1 ∪ . . . ∪ O ′ k since for 1 ≤ i ≤ k, O ′ i ⊆ O i . Of those z points, (z - i-1 j=1 (z c j -x j ))have not yet been seen in an iteration. Hence, these points are definitely not covered byO ′ i ∪ . . . ∪ O ′ k . Furthermore, we know that i-1 j=1 (z c j -x j ) artificial outliers have been defined in O ′ i ∪ . . . ∪ O ′ k in total.This is because all iterations j < i were in case 1, and any artificial outliers present in O ′ j will be propagated to (O ′ j+1 ∪ . . . ∪ O ′ k ) ∩ P j+1 , as these are included in z c j . We subtract x j because these artificial outliers have already been counted by another z c j , and should not be counted again when computing the total amount of artificial outliers. Note that z d j = 0 for all iterations j < i as there were no previous iterations before j in case 2. Since at most n i -z points are covered by O ′ i ∪ . . . ∪ O ′ k , there must be at least one of the modified optimal ball which covers ≤ ni-z k-i+1 . This concludes the proof of the base case. Now, consider the inductive step. We are in an iteration i that is in case 2. There have been i -1 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 ′ j that was covering at mostnj -z k-j+1points. At the time of iteration j, the points of ball O ′ j were charged to distinct points in B(c j , 2r), but not necessarily covered. In the iterations between j and i, however, more points of the ball O ′ j may have been covered. Define O ′ j,unc as the points of O ′ j that are still uncovered at the time of iteration i. Now, for the remaining modified balls, we should have that:EQUATIONSimilar to the base case, (z -i-1 j=1 (z c j -x j )) points will definitely be outsideO ′ i ∪ . . . ∪ O ′ k .In the iterations before j < i in case 1, (z c j + z d j ) points are stored as a credit. We subtract x j from this since we don't want to recount outliers from previous iterations. In each iteration j < i that was in case 2, (z c j + z d j -|O ′ j |) are stored as a credit. Even though B(c j , 2r) is disjoint from the remaining modified balls in this case, B(c j , 2r) can still cover some artificial outliers present in the remaining modified balls. We do not want to recount these for the total amount of outliers in O ′ i ∪ . . . ∪ O ′ k , and hence we subtract x j . Lastly, since the modified balls are disjoint, any points of O ′ j with j < i and iteration j in case 2 that are still in the point set n i are not covered by O ′ i ∪ . . . ∪ O ′ k . We can rewrite this as follows:|O ′ i ∪ . . . ∪ O ′ k | = n i -z -   j<i z d j + j<i in case 2 |O ′ j,unc |   + j<i in case 2 |O ′ j | = n i -z (4)This is because by the definition of z d j ,( j<i z d j + j<i in case 2 |O ′ j,unc |) = j<i in case 2 |O ′ j |. Since at most n i -z points are covered by O ′ i ∪ . . . ∪ O ′ k ,there must be at least one of the remaining modified balls which covers ≤ ni-z k-i+1 . This concludes the proof.Lemma 3.9 (Coverage of B(c i , 2r)). When we are in case 2 of the charging argument for some iteration i, we must have that|B(c i , 2r)| ≥ ni-z k-i+1 -ϵz αk .Proof. We prove the statement by induction on iterations i ≤ k in 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 ′ j has been charged and covered by charging rule I. Hence, B(c i , 2r) cannot intersect any such O ′ j since the points in O ′ j are not in P i . We know that B(c i , 2r) also does not intersect any of the remaining modified balls by our assumption that iteration i is in case 2. Hence, B(c i , 2r) j=1 (z c j -x j ) have been seen in a previous ball B(c j , 4r), for j < i. Hence, |B(c i , 2r)| ≤ z. So, in order to satisfy the dense invariant, |B(c i , 2r)| ≥ ni-z k-i+1 -ϵz αk . Now consider the induction case. We are in an arbitrary iteration i in case 2, and there have been an arbitrary number of iterations j < i in case 2. For iterations j < i in case 2, we assume thatdoes not intersect O ′ 1 ∪ . . . ∪ O ′ k . The ball B(c i , 2r) can cover x ≤ i-1 j=1 (z c j -x j ) artificial|B(c j , 2r)| ≥ nj -z k-j+1 -ϵz αk . Even though B(c i , 2r) is disjoint from the remaining modified balls, it can cover x artificial outliers and z -i-1 j=1 (z c j -x j ) other points. For x we have that:x ≤ j<i in case 1EQUATIONj<i in case 1 (z c j + z d j -x j ) are the total number of artificial outliers from iterations in case 1, and j<i in case 2 (z c j + z d j -|O ′ j | -x j ) are the total number of artificial outliers from case 2. Then, for the total amount of points in B(c i , 2r), we have:EQUATIONThis is because by the definition of z d j , we have that j<i z d j ≤ j<i in case 2 |O ′ j |. So, in order to satisfy the dense invariant, |B(c i , 2r)| ≥ ni-z k-i+1 -ϵz αk . This concludes the proof.Lemma 3.10 (Duration of dense cluster for z is small). Assume that we are currently at time t.Let us consider a level i in which z + 1 ≤EQUATIONB max = B Pi (p, 2r). Assume that n t i -z 2(k-i+1) ≤ |B max |.Then, we can add B Pi (p, 4r) as a cluster in our solution, and this cluster will be dense until time t ′ = t + t * , with t * ≥n t i -z 4(k-i+1) .Proof. The subscript of n i will be omitted for simplicity. At time t, we know that n t -z 2(k-i+1) ≤ |B max |. The resulting cluster B Pi (p, 4r) will be dense as long as B max covers more thanmin z + 1, n t ′ -z k-i+1 -ϵzαk points at time t ′ . Hence, the dense invariant will not be broken as long as B max is greater than z + 1. Let t ′ be the time at which |B max | < z + 1. We can lower bound the time t * between t and t ′ using the change in size of B max . Then, we get the following lower bound:EQUATIONThen, since z + 1 ≤ n t -z 4(k-i+1) by our assumption, we have:EQUATIONThis concludes the proof.Lemma 3.11 (Duration of dense cluster for z is large). Assume that we are currently at time t. Let z + 1 >n t i -z 4(k-i+1)for some level i. Let p = arg max p ′ ∈Si |B Pi (p ′ , 2r)|, and B max = B Pi (p, 2r). Assume thatn t i -z k-i+1 -ϵz βk ≤ |B max |.Then, we can add B Pi (p, 4r) as a cluster in our solution, and this cluster will be dense until time t ′ = t + t * , with t * = Ω( ϵz k ).Proof. The subscript of n i will be omitted for simplicity. At time t, we know that n t -z k-i+1ϵz βk ≤ |B max |. The resulting cluster B Pi (p, 4r) will be dense as long as B max covers more than min z + 1, n t ′ -z k-i+1 -ϵz αk points at time t ′ , with α a fixed constant smaller than β. Hence, the dense invariant will not be broken as long as B max covers at leastn t ′ -z k-i+1 -ϵz αk points. Let t ′ be the time at which |B max | < n t ′ -z k-i+1 -ϵz αk .We can lower bound t * by examining the change in size of B max . Using that n t ′ ≤ n t + t * , we have:EQUATIONNow, solving for t * gives:EQUATIONSince α and β are two fixed constants such that β > α, this gives t * = Ω( ϵz k ). This concludes the proof.Lemma E.1 (Radius guess is small for z is small). Assume that we are currently at time t. Let us consider a level i for which z + 1 ≤n t i -z 4(k-i+1) . Let p = arg max p ′ ∈Si |B Pi (p ′ , 2r)|, where S i is the sample chosen in Algorithm 5, andB max = B Pi (p, 2r). Assume that |B max | < n t i -z 2(k-i+1) .Then, with probability at least 1 -2 e Ψ log k , for Ψ ≥ 1, we have that r < r OPT and until time t ′ = t + t * we do not need to consider the instance for r, with t * ≥n t i -z 2(k-i+2) .Proof. Let O 1 , . . . , O k be the optimal balls at time t. Consider the same charging argument used in Lemma 3.7, where we charged one of the optimal balls to B Pi (c i , 4r) in each level i. Using Equation 4 and the fact that O ′ i ⊆ O i for each of the remaining optimal balls, we know that|O i ∪ . . . ∪ O k | ≥ n t i -z.Then, there must be at least one of the remaining optimal balls covering ≥n t i -zk-i+1 points. Let O i be the largest such ball. Using the Chernoff bound, we show that with high probability, one of the sampled points p ∈ S i is in O i . Define independent random variables X 1 , . . . , X |Oi| , one for each point in O i . Each X j , corresponding to point j ∈ O i , will be 1 if j ∈ S i and 0 otherwise. Define X = |Oi| j=1 X j . We know that E[X j ] = |Si| n t i . Then, using linearity of expectation, we find:EQUATIONThe condition z + 1 ≤n t i -z 4(k-i+1) implies z ≤ n t i 4(k-i+1) ≤ n t i 4 . Then, since |S i | = ψϵ -1 k 2 log k, it follows that |Si| k (1 -z n t i ) ≥ 3 4 ψϵ -1 k log k. Given that ψ ≥ 6β and β > α ≥ 1, this is at least 3ϵ -1 k log k ≥ 3Ψ log k for Ψ ≥ 1.Now, using the Chernoff bound, we find:EQUATIONwhere Ψ ≥ 1.Hence, with probability of at least 1 -2 e Ψ log k , there will be at least 1 point from O i in S i . Let us call this point p. If r ≥ r OPT , B Pi (p, 2r) would cover all points of O i since p ∈ O i and O i has radius ≤ r OPT . However, since |B max | <n t i -z 2(k-i+1) , we must have that r < r OPT . Left to prove is that until time t ′ = t + t * we do not need this instance of r, where t * ≥n t i -z 2(k-i+2) .To this end, let B t max be B max at time t. Consider the situation at time t. We know that |B t max | <n t i -z 2(k-i+1) . Let t ′ be some time after t such that |B t ′ max | ≥ n t ′ i -z k-i+1. Hence, the instance for r becomes valid at time t ′ . We want to 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:EQUATIONUsing n t ′ i ≥ n t i -t * and subsequently solving for t * we find that:EQUATIONThis completes the proof.Lemma E.2 (Radius guess is small for z is large). Assume that we are currently at time t. Let us consider a level i in which z + 1 >n t i -z 4(k-i+1) . Let p = arg max p ′ ∈Si |B Pi (p ′ , 2r)|, where S i is the sample chosen in Algorithm 5, andB max = B Pi (p, 2r). Assume that |B max | < n t i -z k-i+1 -ϵz βk .Then, with probability at least 1 -2 e Ψ log k , for Ψ ≥ 1, we have that r < r OPT and until time t ′ = t + t * we do not need to consider the instance for r, with t * ≥ ϵz 2βk .Proof. Let O 1 , . . . , O k be the optimal balls at time t. As in Lemma E.1, let O i be the largest remaining optimal ball covering ≥n t i -z k-i+1 points.Using the Chernoff bound, we show that with high probability, one of the sampled points p ∈ S i is in O i . Define independent random variables X 1 , . . . , X |Oi| , one for each point in O i . Each X j , corresponding to point j ∈ O i , will be 1 if j ∈ S i and 0 otherwise. Define X = |Oi| j=1 X j . We know that E[X j ] = |Si| n t i . Then, using linearity of expectation, we findEQUATION)Without loss of generality, we can assumen t i -zk-i+1 -ϵz βk ≥ 1, otherwise there would not need to be any points in the ball B Pi (p, 2r) to satisfy the dense invariant, and level i would be trivial. Using this, Equation ( 15) can be simplified as follows:EQUATIONWe make a case distinction. Either z ≥ n t i 2 . In this case, Equation ( 15) further simplifies toEQUATIONRecall that |S i | = ψϵ -1 k 2 log k. Given that ψ ≥ 6β and β > α ≥ 1, we haveEQUATIONfor some Ψ ≥ 1.In the other case z <EQUATIONfor some Ψ ≥ 1.In both cases, using the Chernoff bound, we find that with probability at least 1 -2 e Ψ log k , there will be at least one point p from O i in X i . If r ≥ r OPT , B Pi (p, 2r) would cover all points of O i since p ∈ O i and O i has radius ≤ r OPT . However, since |B max | <n t i -z k-i+1 -ϵz βk < n t i -z k-i+1 ≤ |O i |, we must have that r < r OPT .Left to prove is that until time t ′ = t + t * , with t * = Ω( ϵz k ), we do not need this instance of r. To this end, let B t max be B max at time t. Consider the situation at time t. We know that |B t max | <n t i -z k-i+1 -ϵz βk . Let t ′ be some time after t such that |B t ′ max | ≥ n t ′ i -z k-i+1 . The cluster B Pi (p, 2r) in level i is now covering sufficiently many points. We want to derive a lower bound for t * = t ′ -t to complete the proof. By examining the change in the size of B max and using that n t ′ i ≥ n t i -t * , we deriveEQUATIONEQUATIONas a lower bound for t * . Solving for t * givesEQUATION)Since β is a constant, this is in Ω( ϵz k ). This concludes the proof.F Missing proofs from Section 3.5Lemma F.1. The amortized update time of our dynamic algorithm is O(ϵ -3 k 6 log(k) log(∆)).Proof. Let us fix an arbitrary time t and assume that at time t, there are λ ≤ k clusters. Let time t ′ = t + t * be the time at which we need to invoke Procedure 5 on an arbitrary level i ≤ k, due to the dense invariant being violated. We have two cases: EQUATIONϵn t i k 2 ).Observe that in both cases, we have a worst-case guarantee for the number of time steps during which the cluster B Pi (c i , 2r) remains dense. This, in turn, allows us to achieve a worst-case amortized update time, rather than the weaker notion of expected amortized update time. We analyze the update time of each case separately.Let us start with the first case which is z + 1 ≤n t i -z 4(k-i+1) and suppose that we find a cluster such that |B Pi (c i , 2r)| ≥ n t i -z 2(k-i+1) at time t. We know that t * ≥n t i -z 4(k-i+1) . The cost of reclustering levels i, . . . , k according to Lemma 3.3 is O(n t ′ i ϵ -1 • k 3 log k), with n t ′ i ≤ n t i + t * . Then, the amortized update time of an arbitrary update operation is O(1 t * (n t i + t * )ϵ -1 k 3 log k) = O( n t i t * ϵ -1 k 3 log k). Since z ≤ n t i 4(k-i+1) , we obtain n t i t * ≤ n t i • 4(k-i+1) n t i -z ≤ 4k • n t i n t i -z ≤ 4k • n t i n t i (1- 1 4(k-i+1) ) = 4k • 4(k-i+1) 4(k-i+1)-1 = O(k) . Thus, O( n t i t * ϵ -1 k 3 log k) = O(ϵ -1 k 4 log k). Now, we consider the second case. Using a similar analysis as in the first case, we have t * = Ω(ϵn t i k 2 ). Then, the amortized update time of an arbitrary update operation is O(n t i t * ϵ -1 k 3 log k) = O(ϵ -2 k 5 log k).After reclustering levels i, . . . , k, there is no longer a lower bound for t * for levels j < i. Thus, it could happen that such a level j needs to be reclustered soon after time t ′ . Since j < k, this leads to an extra factor k such that the final amortized cost is O(ϵ -2 k 6 log k).Finally, we need to consider the case that offline clustering fails for a level i. That is, we fail to find a ball covering sufficiently many points in Procedure 5. If offline clustering fails on some level i in case 1, meaning we fail to find a ball such that |B Pi (c i , 2r)| ≥n t i -z 2(k-i+1), then Lemma E.1 proves that with probability 1 -1 e Ω(log k) , the guess r is small (i.e., r < r OPT ) and indeed, remains small and we do not need to consider this guess until a time t ′ = t + t * where t * ≥ n t i -z 2(k-i+2) . At time t ′ , we recluster levels i, . . . , k. Then, since we are in the first case, we have z ≤ n t i 4(k-i+1) . Thus, the amortized update time of an arbitrary update operation in this case isO( 1 t * (n t i + t * )ϵ -1 k 3 log k) = O( n t i t * ϵ -1 k 3 log k) = O(ϵ -1 k 4 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 a ball such that |B Pi (c i , 2r)| ≥ ni-z k-i+1 -ϵz βk . According to Lemma E.2, the guess r is small (i.e., r < r OPT ) with probability 1 -1 e Ω(log k) and indeed, remains small and we do not need to consider this guess until time t ′ = t + t * where t ′ = Ω( ϵz k ). This leads to an amortized update time of O(ϵ -2 k 5 log k). As mentioned above, the running time needs to be multiplied by an additional factor k to account for the possible need to recluster lower levels.Finally, we need to consider O( log ∆ log(1+ϵ) ) guesses for the optimal radii. For small ϵ, this is in O( log ∆ ϵ ). Thus, we derive the final amortized update time of O(ϵ -3 k 6 log k log ∆).Lemma G.1. Let (M, d) be a metric space and ϵ > 0 be an accuracy parameter. The spread ratio ∆ = dmax dmin of all points ever inserted is assumed to be bounded. There exists a randomized fully dynamic algorithm that maintains a discrete k-center solution that allows up to (1+ϵ)z many outliers on the current set of points. At every point in time t, the current clustering with centers c 1 , . . . , c λ is a (4 + ϵ)-approximation to an optimal solution for the (k, z)-center problem with high probability and c i ∈ P t for all i ≤ λ. Upon insertion or deletion of a point, the data structure is updated in amortized update time O(ϵ -3 k 6 log(k) log(∆)).Proof. Let r and i be fixed, and c i be the center of cluster C i = B Pi (c i , 4r). As long as c i is not deleted, we report c i 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.After the deletion of the point c i , we consider two cases:min z + 1, ni-z k-i+1 -εz αk ≤ 0 or min z + 1, ni-z k-i+1 -εz αk > 0. If min z + 1, ni-z k-i+1 -εz αk ≤ 0, then n i < (1 + ε)z as i ≥ 1 and α > 1.Hence, we can report all the n i points as outliers and stop. We next consider the second case. The dense invariant states that |B Pi (c i , 2r)| ≥ min(z + 1, ni-z k-i+1 -εz αk ). Therefore, |B Pi (c i , 2r)| > 0 holds in the second case, and there exists a point p ∈ B Pi (c i , 2r). Then we report an arbitrary point p ∈ B Pi (c i , 2r) after the deletion of c i . Note that we do not replace c i by p in our data structure, and c i 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 i ⊆ B(p, 6r). This implies that any feasible solution with radius 4r for the non-discrete version can be used to report a feasible solution for the discrete version. Also, see Figure 4 for a visual representation. Let q ∈ C i . We show that q ∈ B(p, 6r). Since q ∈ C i = B(c i , 4r), we have d(q, c i ) ≤ 4r. Moreover, d(c i , p) ≤ 2r since p ∈ B(c i , 2r). Then by the triangle inequality, we haved(q, p) ≤ d(q, c i ) + d(c i , p) ≤ 4r + 2r = 6r.To report a solution for the discrete version, it is enough to keep B(c i , 2r) ∩ P i . Note that our data structure already stores C i ∩ P i , and since B(c i , 2r) ∩ P i ⊆ C i ∩ P i , the space complexity and time complexity remain the same. •EQUATIONThe authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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. 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 no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe 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)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 a 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 is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
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 to 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• 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.In fact, original balls O1, • • • , O k can overlap, but we can make them disjoint by assigning any point that is inside multiple balls to just one of them arbitrarily. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: The algorithm is randomized and works only against oblivious adversaries. This is a shared characteristic with the previous paper on this topic.

The 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.

Overall, even though this is a solid contribution to the study of the problem, this is not a breakthrough.

I also wish the authors did a better job highlighting the technical ideas that lead to the improvement over the previous algorithm.
questions: questions: Is there a good reason why the algorithm is randomized? What are the obstacles to obtaining deterministic algorithms in this model?

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?
limitations: limitations: No specific societal limitations to address. This is a theoretical work concerning a traditional computational problem.
paper_summary: paper_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. 

The 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:

- level invariant: Each level $i$ has a cluster $C_i$ such that $P_{i+1} = P_i \backslash C_i$.
- dense invariant: For each center $c_i$ in $F_r$, $B(c_i, 2r)$ covers sufficient points in $P_i$.

The authors prove that it is a $(4+\varepsilon)$-approximation algorithm with $O(\varepsilon^{-2}k^6\log k\log \Delta)$ expected amortized update time.
strength_weakness: strength_weakness: - the update time complexity $O(\varepsilon^{-2}k^6\log k\log \Delta)$ is not competitive, particularly for large $k$.
- The paper does not provide empirical results or practical evaluations of the algorithm, which could demonstrate its performance in real-world scenarios.
questions: 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$.
- 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: limitations: thoretical paper
paper_summary: paper_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.

The 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.

From 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:

*  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);
* 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; 
* grow a ball of radius 4r around the center c; 
* remove the points belonging to the ball from the current point sets, and continue with the next iteration (level)
* the number of levels is bounded by roughly k
* the centers computed in each level are output as the solution the (k,z) clustering problem

The 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.
strength_weakness: strength_weakness: * 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.

* 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.
questions: questions: Minor comments:

Lines 17-29, you should back up with citations the applications of clustering across many subfields of computer science and beyond
Line 36, 'various complications' sounds a bit odd (maybe challenges would be a better fit here)
Line 196, n_i, \alpha never defined before in text
Line 219, should your j start from 1 and not from i? -- similar comment for Definition 3.2

Major comment/question:
Line 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: limitations: Yes,
paper_summary: paper_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.
strength_weakness: strength_weakness: 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})$​.
2. 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.
3. 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].
questions: 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)$?
2. 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?
3. What is the size of your memory usage?
limitations: limitations: Please see weakness.

Comments: comment: Thank you for your response!

> we have discovered that our dynamic algorithm not only can handle oblivious adversaries but is even adversarially robust

This is very interesting and if true, it definitely makes your algorithm more interesting. I'm very curious about this but I'm not sure I'll have time to reread your paper to see if I have any doubts about this. Whatever happens to your paper, it would of course be great to explicitly address this in any future version of the paper.
Thanks for the clarification. I will keep my original rating.