Faster Query Times for Fully Dynamic $k$-Center Clustering with Outliers
Authors: Leyla Biabani
Annika Hennes
Morteza Monemizadeh
Melanie Schmidt
Venue: NeurIPS 2023 poster (2023)
Keywords: $k$-center clustering
outliers
dynamic algorithms

Abstract: Given a point set $P\subseteq M$ from a metric space $(M,d)$ and numbers $k, z \in N$, the *metric $k$-center problem with $z$ outliers* is to find a set $C^\ast\subseteq P$ of $k$ points such that the maximum distance of all but at most $z$ outlier points of $P$ to their nearest center in ${C}^\ast$ is minimized. We consider this problem in the fully dynamic model, i.e., under insertions and deletions of points, for the case that the metric space has a bounded doubling dimension $dim$. We utilize a hierarchical data structure to maintain the points and their neighborhoods, which enables us to efficiently find the clusters. In particular, our data structure can be queried at any time to generate a $(3+\varepsilon)$-approximate solution for input values of $k$ and $z$ in worst-case query time $\varepsilon^{-O(dim)}k \log{n} \log\log{\Delta}$, where $\Delta$ is the ratio between the maximum and minimum distance between two points in $P$. Moreover, it allows insertion/deletion of a point in worst-case update time $\varepsilon^{-O(dim)}\log{n}\log{\Delta}$. Our result achieves a significantly faster query time with respect to $k$ and $z$ than the current state-of-the-art by Pellizzoni, Pietracaprina, and Pucci, which uses $\varepsilon^{-O(dim)}(k+z)^2\log{\Delta}$ query time to obtain a $(3+\varepsilon)$-approximation.

Faster Query Times for Fully Dynamic k-Center Clustering with Outliers
Leyla Biabani
Annika Hennes
Eindhoven University of Technology Eindhoven, The Netherlands
Heinrich Heine University Düsseldorf
Düsseldorf, Germany
1. biabani @tue. nl
annika hww.ee@hhu....mm de
Morteza Monemizadeh Eindhoven University of Technology Eindhoven, The Netherlands m m.mommizadee@uue....... nl
Melanie Schmidt
Heinrich Heine University Düsseldorf Düsseldorf, Germany ms mshmidt@@hu.. @t@hhu.dee
Abstract
Given point set P C M from a metric space (M, d) and numbers k, 2 E N, the metric k-center problem with outliers is to find set C' S P of k points such that the maximum distance of all but at most outlier points of P to their nearest center in C* is minimized. We consider this problem the fully dynamic model, i.e., under insertions and deletions of points, for the case that the metric space has a bounded doubling dimension dim. We utilize a hierarchical data structure maintain the points and their neighborhoods, which enables us to efficiently find the clusters. particular, our data structure can be queried at any time to generate a (3 + apprroxmmmte solution for input values of k and in worst-case query time E O(dim) & log log log A, where A is the ratio between the maximum and minimum distance between two points in P. Moreover, it allows insertion/deletion point in worst-case update time O(dim) log n log A. Our result achieves a significantly faster query time with respect to k and than the current state-of-the- art by Pellizzoni, Pietracaprina, and Pucci [18), which uses E O(dim) (k 2)² log A query time to obtain (3 + -aapproxie solution.
Introduction
Clustering is fundamental problem in machine learning and it has applications in many areas ranging from natural to social sciences. As basic unsupervised learning method, it allows us to find structure in data. Classical center-based clustering methods for objectives like k-means, k-median and k-center have been around for many decades [9] 16]. Since the beginning of clustering, the data to be analyzed has changed dramatically, raising new challenges for clustering methods. Data nowadays comes in large to huge batches and is often prone to inherent change: Content social media platforms constantly added, re-organized or deleted, streaming services handle an always ongoing flow of people starting and stopping to watch, tweets the fastest method to distribute news and delete them later if desired. Data analysis methods thus face the challenge of analyzing huge amounts of data, ideally permanently updating their solution.
In this paper, we consider the problem of dynamic k-center clustering with outliers. The (metric) k-center problem is to find a set C* C P of & points such that the maximum distance of all points of P to their nearest center in C* is minimized. This objective is well understood, 2-approximations for the problem are known
and better approximations not possible unless P equals N. [14]
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Fully dynamic k-center algorithms without outliers.
Year
Ref.
Metric
Update time
Approx
2018
general
amort. )
2+
2019
Eucl. Rd
amort. O( Log A log n)
16
2021
doubl. general
(((im)) log log log A
2 +
2023
amort. polylog( (n, A))
2 +
Considering outliers for k-center is very natural. Since k-center minimizes the maximum radius, a single measuring error can destroy the structure completely. Thus, the (ks 2)-center problem allows us to ignore 2 points. These belong to no clusters but are deemed to be outliers, and so they are ignored when determining the maximum radius of cluster. The concept was introduced in 2001 by Charikar, Khuller, Mount, and Narasimhan [6] who one result provide 3-approximation for k-center with outliers. This variant has since been the subject of many papers, and the best-known approximation algorithm for it, which gives 2-approximation, was derived as recently as 2016 (2).
In parallel, fully dynamic k-center algorithms (without outliers) have been developed M I0 which work with a changing point set given as a stream of insertions and deletions. All these maintain a data structure that allows for continual updates to keep adapting to the changing data. An overview is given in [T All results in this table support some form of membership queries: Given a point, return the cluster/ center of the cluster of that point in the approximate solution. This type of query can typically be answered in time O(1). Reporting the centers takes more time or is not necessarily explained how to do.
Now the challenge is to combine the two parallel developments into a fully dynamic algorithm for (ki z)-eete clustering. We discuss the setting more precisely and then our results and related work.
Our setting We say that metric space has doubling dimension dim if dim is the smallest positive integer such that any ball of radius can be covered by at most 2dim balls of radius r/2. For an overview of this concept, we also refer the reader to [12 II. Let (M, d) denote such a metric space and let P S M be a set of points. By dmai = inf fd(2,, y) y E P. x * y} and dmax = sup ( ddx,y)) w) xz E P) we denote the minimum and maximum inter-point distance within P. respectively. Without loss of generality, we assume that dmin 2. Let A == dmax dmin be the aspect ratio of P.
We are observing a dynamic stream, i.c., we start with point set P = 0 and then process a sequence of operations whose length is unknown priori. Each operation either adds a point from M to P deletes a point which is currently in / from P. We assume only deletions of points that are currently present are allowed, and we also assume that we can always compute multiply all times mentioned in this paper by the time necessary to make one distance computation). We refer to the point set after time (i.e., after operations happened) as Pt. If it is clear from the context, we will sometimes drop the subscript. We assume that dmax and dmii are fixed throughout the whole sequence of updates, i.e. dmax dmin- Therefore, A is an upper bound on the aspect ratio over all updates and is known in advance. This is in accordance with a sequence of other works
time (11) (otherwise,
sup(d(ax y) y.y E Pt. L 2 0}, and analogously for
10 19].
The problem that we address is the dynamic k-center problem with outliers or in short (k, 2)- center problem: Given P3 and numbers k and z, produce set C CC P. of size most k such that the maximum distance of all but at most points to their nearest neighbor is minimized. More formally, minzcp,,izis= max P. Z min.ec d(x, c) is minimized among all possible choices of C with IC' < k.
'Notiee the small detail that we do not ask to compute Z but only to provide centers that are good centers under the assumption that most points can be ignored. In the offline setting, finding Z can be done by assigning every point in P to its closest point C' and then ignoring the 2 points farthest away. the dynamic setting and with our data structure, we could also produce the outliers. However, we believe that the outliers are less interesting than the centers, and since there could be substantially many outliers, we rather only report the cluster centers to avoid linear dependence on
2

---

Table 2: Fully dynamic k-center algorithms with outliers and their update/query times.
Year
Ref.
Metric
Update time
Query time
Approx
2022
general
( + log A)
( (k- + 2)2 A)
14+
2023
18
doubl.
goraim: log A
Ttaim (A: + x)² log A
3 3
2023
doubl.
0 galm + 2) log"
AA
O(( gaint + =)2
س + 2))
3+
now
Thm
1.1
doubl.
sordimn
log log A
pordims k log vi log log A
3 3
Our focus is on building a dynamic algorithm that has low update time for insertion and deletions. We are allowed to store P (and additional information). Our aim is to achieve an update time for our data structure that is independent of Ic and query time that is at most linear in k. For this, it is necessary to consider a restricted model, as Bateni et al. [ showed that in arbitrary metric spaces. an update time of (2kk)) is necessary. We consider metric spaces of bounded doubling dimension. Obviously, time ((k) is necessary to return an actual solution, so we distinguish between update time for insertion and deletions of points and query time for obtaining solution from the data structure.
Our result compared to related work We present a deterministic (3 é) approximmatoonnn algorithm for the k-center problem with outliers in bounded doubling dimension that is fully dynamic, i..., points can be inserted and deleted. Our algorithm is based on a data structure that requires space linear in and does not need to know k and in advance. As result, we can answer queries for all and 2, or in other words, and can be part of the query. Moreover, our algorithm does not require knowledge of the doubling dimension dim of the underlying metric space, and it only appears in the analysis.
Theorem 1.1 (Main theorem). Let (M, d) be a metric space of bounded doubling dimension dim, and let e > 0 be error parameter. There exists deterministic dynamic algorithm that allows the insertion or deletion of points from M using worst-case E- -O(dim) log n log A update time. Moreover, at any time t. it can be queried by parameters k and compute (3 -)-pproxximate solution for the k-center problem with outliers of Pe using worst-case e -0(dimm) k log log log A query time, where Pe is the set of points that are inserted but not deleted up to time f, and n is the size of Pt.
The first approximation algorithm for this problem has been obtained by Chan, Lattanzi, Sozio, and Wang in 2022 [4). which has an approximation ratio of 14 + E. Very recently and in independent work, Pellizzoni, Pietracaprina, and Pucci [8] derived an algorithm with approximation ratio 3 + e. For the problem of distributed k-center with outliers, De Berg, Biabani, and Monemizadeh [7] give a randomized dynamic algorithm that also achieves a guarantee of + E with failure probability 5. Both of these and also we develop algorithms that answer solution queries rather than membership queries, i.e., they can produce a center set at any time and this set is an approximately good solution for the current k-center with outliers instance. We state the update times (for insertions and deletions of points) and the query times (for reporting the current approximate solution) of these and our approaches in Table
All three known results have dependency on (k + 2)² in their query time which we improve to a linear dependence on k and no dependence on z. This gives our approach an advantage even if k or are only mildly dependent on n: Already for k Ollogn) n) and E (V). the query complexity of [8] would be linear in n compared to the poly-logarithmic dependency in terms of n for our query time. More interestingly. for realistic regime where is an epsilon-fraction of n, the query time of the dynamic algorithm presented in [18] has quadratic dependency in terms of n while our query time still has logarithmic dependency in terms of n and linear dependency terms of k. [ also states bicriteria approximation where the number of outliers can be violated with improved running time, but the dependency on is still quadratic. When comparing to 77. should be noted that their algorithm is only applicable to the Euclidean metric space, is randomized and only works against oblivious adversaries. Further, the coreset size (and the space complexity) of the algorithm in 7 is
Okk dim log A + z). In the streaming model, in order to extract the solution, one needs to run an offline algorithm on the coreset. In this way, the query time of this algorithm is O(kx2 log .r) = O(k(22 + 1:2) 22dm log² A) which significantly worse than the query time of our algorithm.
3

---

The main difference of our approach is that it makes the greedy algorithm for k-center with outliers dynamic while the previous dynamic algorithms extract a coreset and run the greedy algorithm on this coreset. Known dynamic algorithms [4] 7 18] for the k-center problem with outliers maintain a coreset after every update. partieular, in [88 they extract the coreset by simply reading the solution from the cover tree. To extract an approximate solution for this problem, one needs to run a known (offline) greedy algorithm on this coreset. In this way, the query complexities of those algorithms are dominated by the running time of the greedy algorithm. The novelty of our dynamic algorithm is that we make the greedy algorithm itself dynamic. To this end, we use heap data structures to compute a ball that covers the maximum number of points, and dynamic neighborhood sets to obtain points in the expanded maximum ball and update their corresponding keys in the heap to recursively find the next maximum balls.
Navigating nets. The state-of-the-art algorithm for the fully dynamic k-center problem (without outliers) in doubling metrics, developed by Goranci et al. [TO] uses navigating nets originally introduced by Krauthgamer and Lee [1]. The basic idea of a navigating net is to start with the point set Pt as the base net N1 and then compute coarser and coarser variants of it, resulting in a hierarchy of nets N1. N2....... ......... For every level in this hierarchy, the points are good representatives of the points in the level below but the higher we get in the net, we have fewer points that are better separated. More precisely, following Krauthgamer and Lee [[5]. every level is a so-called r-net of the level below it. An r-net on a set X is subset Y C X that satisfies two properties:
1. Vp X3 E Y: d(p. v) < (Covering) 2. Vx, y E Y: d(x, v) 2 (Packing)
In a navigating net, one always assures that N, is an r-net of N2/2. Assume that the minimum inter-point distance dmmi satisfies dmin 2 and that the ratio between maximum and minimum inter-point distance is A. Then a navigating net with O(log A) levels can be computed in a greedy fashion. Intriguingly, one show that in the resulting navigating net, the lowest level with |N, s k provides an 8-approximation for the k-center problem (without outliers, i.e., 2 0). This was first observed (in the context of streaming algorithms and there known as the doubling algorithm) by Charikar, Chekuri, Feder, and Motwani [5]. An additional trick to improve the approximation ratio was discovered by McCutchen and Khuller [17 (again, in the setting of streaming). They observed that the quality of the solutions depends heavily on what the radius of the lowest level is, and that this radius can be shifted by small amounts, and one of the shifted versions will give a 2 + approximation. By maintaining the navigating net structure and using a similar shifting trick, dynamic k-center algorithms maintain enough information to answer queries by checking one or a few levels of the resulting navigating net and reporting the points on that level as the solution, as for example in [0
Challenges with outliers. there is no level in the navigating net which provides a good solution in itself. We know that optimal (k, z)center solution has a radius that lies between the radius of a k-center solution (because any k-center solution is feasible for the (k, 2)-center problem) and the radius of a (k + z)-center solution (because any (k, z)-cetr solution is feasible for the (A: + 2)- center problem). But Figure [ shows, nei- ther of the two choices may provide a good es- timate for the optimum (k: -ceenterrr solution. Say level r1 is the first to satisfy [N,, < + z and level 122 is the first to satisfy [N,2 < k. Then the points in Nr, are feasible solution for the (k, =)-cete problem, but their radius may be too large, while the radius of the solu- tion in Nr, is guaranteed to be small enough, but these points may not constitute a feasible solution for (k; z)-center. This because every point in N2 represents several points in the levels below it. So we cannot simply divide the k +
For the (k, 2)-center problem, the challenge is that
OPT
Figure 1: For k = 1 and 2 = 3, k-center and (k: + z)-center provide bad estimations for the best (k, z)-eenter solution in this example. We see: (a) Dashed Ball: Optimum solution for (k: 2)-center. (b) Small Balls (too small): Optimum solution for (cettee (c) Not drawn: the optimum solution for k-center is a ball around all points (too large).

---

points into k centers and 2 outliers (see Figure DT. Therefore, there is no individual level which we can query to obtain solution. Instead, we need compute a solution from the navigating net levels while making sure not to lose too much in terms of quality and query time.
Pellizzoni et al. [8] base their approach on the so-called "cover tree" data structure, which is similar to that of navigating net, to compute coreset from which they construct the final solution. In their approach, they find the lowest level with |.Vr| I 20(dim) dim (k: + 2) and demonstrate that such N, serves an E-coreset for (ki, 2)-eeterr. However, since is not feasible solution, they utilize 3-approximation greedy algorithm to obtain a (3 + aapproximate clustering, which requires a time complexity of ()== 2 (k + 2)²). ). In this paper, we strategically integrate additional information at each level to directly emulate the offline 3-approximation greedy algorithm by Charikar et al. [6] in the dynamic setting. This approach enables us to achieve a time complexity that is linearly dependent on k and remarkably independent of 2.
2 Our data structure
In this section, we describe our data structure, which has Ollog A) levels. In each level r, we have net N,, which is an r-net of N,,2. For each point p E Nr, we keep its weight wy (p) and local neighborhoods B2,, and B3 p.r. which are balls of radius (1 + (e)))r and (3 O(e))r respectively. Then we maintain max-heap H,, which is designed to store the total weights of neighborhoods By,,, for all p E Ny. We also keep rep, for each point p P, which is the representative of p in N,. Below, we provide a detailed explanation for elements of our data structure.
Input and set R. To start building our data structure, require three input parameters: A, 6', and 3, where 0 < 6' < 1, and 2 < 8 < 1. A denotes the spread ratio of the underlying point set P and g is the given error parameter. We utilize 3 to define R == {0} U 2 0 < t S [log2 1,,,, 2} as set of levels. Additionally, we define e == 2llog='J, This implies that e' 6/2 < & < e'. Furthermore, if T E R, then either Er E or < B.
Nets Ny. We maintain net N₂ for each E R. satisfying the following conditions: No = Ng P.. where Pt is the set of points at time t, and for r > 8, N, is an r-net of /r/2. For p E N, and q E N2.2, we say p is a parent of q (and q is child of p) d(p, q) S r. In our data structure, we store all the parents and children for each point for all the nets. It important to note that each point can have at most 20(im)) parents or children. In the full version, we explain how to handle each insert/delete in time (0dim) log A.
During the paper, we may refer to Ner for 0 < er < B, which means er & R. Besides, note that since dmii = and 3 2, Pt is an r-net for any S r S B. To solve this issue, we define N, := P. for any 0- < < 3, however, we do not explicitly keep any r-nets for 0 < r < 3 in our data structure to prevent redundancy.
Representatives rep, and weights wy. For all r R, we inductively define functions rep,: P. - Nr such that each point p E Pt has a unique representative (p) in net N,.. To define rep, (p), we consider three cases. First, if p N,, then we define (p) == p. Second, if p & N, but p E Nr/2, we uniquely choose one of the parents of p in N, as rep, (p). Third, p & N,y2 and therefore p & N,, we define (e) = rep, (rep,/2(p)) Again to avoid inconsistency, we define (p) == p for any 0 < < B, but we do not store this explicitly. We show in Lemma 2.1 that the distance between each point p and its representative in N, is at most 2r.
Next, we define a weight function w. for every level. For every point p E Nr. its weight (x) denotes the number of points that p is representing in N,. More formally, w,(p) kg E P. (g) = =p For set X C Nr, we define wx(XX = EpEx wr)pp. Equivalently, w, (X) = (u E P. rep, (v) X3/. Note that the sum of weights of all representatives at any level is equal the total number of points, so w,, (N,) = =|Pa] for all E R.
Since we store all the parents and children, we can easily update the representatives and therefore the weights after each insert/delete. The details are presented in the full version.
5

---

Balls B' and B³. Let r E R. For every point E Ner, we maintain the close neighborhood
By,- == (p. (1 + ( and the extended neighborhood B p.r == (p, (3 8E)r) n n. where (p >) = {q E M d(p. q) }} denotes the ball of radius À around p in the metric space M. Then B == [B, I R. P Ner and B = {B3 r E R, p E Ner are the collections of local neighborhoods at different scales. As mentioned Lemma 2.2 the size of each of these neighborhoods is at most 20(dim) /=dim. We also show that we can update these neighborhoods in time 20(dim)) 2dim g-2im log A after each insert/delete in the proof of Lemma 2.3
Heaps H,, For every E R. we maintain a max-heap H, of the set {(p, Wer ( p. 1p N representing the weight of the close neighborhood of any point in level r. With H, [p] we denote the value of the max heap element with key p. Since B might change, we need to find the position of the respective heap element by its key p. Hence, for any level r, we keep a pointer from every element in N, to its corresponding element in Hr,
Whenever an update happens to set Bp.- for some point p E Ner. we need to update the value of Wer( ( (rr) as well as the value of Hz[p]- Each update in the max-heap H, can be done in Ollog n) time using the standard max-heap operations. In the full version, we show that 20(dim)e dim log A updates happen to set B!. Therefore, we need (0dim) dim log A log time to update the heaps.
few lemmas about our data structure. Now we mention a few useful lemmas about our data structure. The formal proof' can be found in the full version. The first lemma is about the distance of each point to its representative, which is bounded because of a geometric series argument.
Lemma 2.1. Let p E P. and R. Then d(p, re), 2r. In particular, d(p, re) S 2er, where e 2l for the error parameter e'.
We next discuss the size of close neighborhoods and extended neighborhoods. Lemma 2.2. Let E R. and E Ner. The sets By and By defined above are of size at most 20(dim) g- dim, In particular, the size is Os ) constant doubling dimension dim.
In the next lemma, we show that the update time is logarithmic in the spread ratio and the size of Pt- Lemma 2.3. Let n be the size of point set Pt. Then after insertion/deletion of any point to Ps, we can update our data structure in time 20(im) dim log A log
Besides insertion and deletion updates, our data structure supports solution queries: in every time step, it can produce solution in the form of center set and a radius. We will discuss this in more detail and present algorithm that outputs a (3 + -appooaapioinniaioon in time = (((im))) k log n log log A in the following section.
3 Our algorithm
Overview For given level in R and number of centers kt, the main procedure MAXCOVERAGE produces a set of k centers and a value outliers Weight. One run of this procedure is deemed successful if outliers Weight S at the end. Indeed, we will later show that outliers W Weight is an upper bound on the actual number of outliers in the clustering with centers C and radius (3 + 10s)r, which implies that this is feasible solution. The algorithm FINDCENTERS finds one such level for which MAXCOVERAGE is successful. We also ensure that this level is chosen such that MAXCOVERAGE not successful on the next lower level r/2, which guarantees that the radius of our solution does not deviate from the optimal solution by too much.
In our algorithm, repeatedly find areas that subsume the most points. In order do this efficiently, we maintain the collections of close neighborhoods and their weights in max-heaps. Fix a level r E R. For iterations, the root node of the current heap corresponds the next center of our solution. After picking it, we mark points in the extended neighborhood because our final approximate solution will cover these points and they should not contribute the weight of other neighborhoods anymore.

---

As these points are now cov- ered, we decrease the weights of heap elements represent- ing points therein accordingly. These steps are performed by MAXCOVERAGE. Note that for maintenance reasons, one run of FINDCENTERS should leave the original heaps unchanged. We could make a copy of the heap before processing it in MAXCOV- FRAGE, but it is faster to work on the original heaps and just roll back all the updates done dur- ing MAXCOVERAGE of the algorithm, as described in Lemma 3.8
Procedure MAXCOVERAGE(KR)
+ 0, Marked <- 0, oulliers Weight &- n Let H be copy of H, 3 for = 1 to k do
Let be the key with maximum value in heap H
s
CU
6
for each y E B% such that & Marked do Marked Marked for each a E By,r do L Decrease H [[ by (vr(v) outliers Weight +- outliers Weight - Werr (V)
7
10
return C, oulliers Weight
the end
Algorithm FINDENTESS(K)
Output: :Centers C' of a (3 + 100))-aaproximmaton for (k, -eenter 1 if MAXCOVERAGE(R: 0). outliers Weight < +then
remains to find a good value for т. By applying binary search, we find a radius r such that the value of outliers Weight 2 outputted by MAXCOVER (OE(E (GE(K, r) is at most while the respec- tive output on the lower level r/2 more than z. Note that it pos- sible to find such a pair of sub- sequent radii via binary search
return MAXCOVERAGE(K;
3
By performing binary-search on R. find f such that MAXCOVERAGE k, f). outliers Weight S z, and
MAXCOVERAGE k. f f/2). outliers Weight > 2 if
4 return MAXCOVERAGE(H,
although the search space might
not be monotone. In the special case that there are at most 2 points in total, we can just set the radius to O. This is done in Algorithm (F [[FINDCENTERS( z)).
Analysis Next, we prove the approximation guarantee and time complexity of our algorithm.
Let and & be fixed, and let E [1, k] be an integer. For any point y Ner- we say y marked after the i-th iteration of the loop in Line of MAXCOVERAGE, if y E Uj=11 B and we say it is unmarked if it not the case. For simplicity, we may refer to a point as marked or unmarked without specifying the iteration if it is clear from the context. We define set U, := {u E Ner y & U, B3 ,r the set of unmarked points after the i-th iteration. We next define =p E Pt (p) & UJ i-th iteration of the loop. Equivalently, O {u E P. reper (p) E U.). After the i-th iteration of the loop in Line 3. for each y E Ner. H, [y] is the total weight of unmarked points in B1 yir
13 ,r the set of points that are considered outliers after the
Lemma 3.1 (Invariant for heaps). Let l be an integer, 0 < i < k, and r E R. Then for any E Ner 1 n U.) after the i-th iteration.
holds H, Wer (B,,r
(INDCENTERS(K; =) returns a solution when outliers Weight < z. To show that this solution is feasible, it remains to prove that oulliers Weight is upper bound on the actual number of outliers of this solution.
Lemma 3.2 (Feasible solution). Consider a radius E R. and an integer k. Then MAXCOVERACE((K r) returns k centers and a value outliers oufliersWeight, such that the total number of points in Pt that are not within distance (3 + 105)r of these k centers is at most outliers Weight.
Proof. Let outliers Weight denote MAXCOVERAGE((,.)) outliers Weight. We want to prove that MAXCOVERAGI(K:.)) returns (a, (c...., (x) such that IP, \ UjSR Ball(c,, (3 + 10s)r) s outliers Weight is decreased by wer for every y
outliers Weight. In every iteration B3 \ Marked. After processing y, we add it to Marked. This way, we ensure that no is charged twice. Therefore, by the end of the algorithm, outliers Weight is decreased by wer (U)ra Dr
7

---

Hence, in the end, the value of outliers Weight is
outhers Weight -Wer (U Bis,r)
B
j5k
= = - Kp E P. rep reper
E U B p
USk
- (3 + 8E)r holds for at least one j I k by definition of Be Using Lemma 2.1 this implies d(c,. I d(cy. + (p),p) I (3 85)r 2er (3 + 10e)r. Hence, Epe Ps rep (p) UjSr B _ E
For all p E Pt. if (p) E UjSt B then
Pt 3j S k: d(c,.p) S (3 + (r))r and therefore
outliers Weight 2 P. Hp P. 3j k: d(cr,p) (3 10s)r)
= Pa U jsk
Ball(e,, (3 + 10:)r) n P.l
Consider fixed optimal solution. The following insight is crucial for proof: In every iteration of MLACOOERAGEECE r) for 2 OPT, we select a ball that covers sufficient number of unmarked points. To be precise, it exceeds the number of currently considered outliers in any optimal cluster.
Lemma 3.3 (Invariant for picking c,). Let 2 OPT, where r E R. and let c* E Pt be center of an optimal solution for k-center with z outliers. Assume that we execute MAXCOVERAGE (k, r). Then for any i E [1, k), the 4; picked in Line 4 is such that Ball(c", (PT)
I wer (B o4 (U-))..
Proof. We define è (c"),,()), the representative of c* in Ner- Recall that B {y E Ner d(c, y) S (1 + 4e)r). Lemma 3.1 states that Hly) Wer(B), (B),, O U--1) holds for all y E Ner after the (8 - 1)-th iteration. Since c; is on top of the max-heap H, we have Wer (er n Ut-1) S Wer ( (U;-1). Therefore, it remains to show that Ball(c", OPT) (B) 0, nU;-1).
According to the definition of representative and weight function, we first have
[aal((c,, OPT) no.-1|
E
Wer
yErep (Ballfe ,PTT)OO_-)
We next show that for any point p E Ball(c", OPT) P., its representative on level er lies in B ie. (p) E By Let p E Ball(c,, OPT) n P. be an arbitrary point, then d(c", p) I OPT < By the triangle inequality, d(ć, rep,, (p)) I d(č, c*) + d(cc", p) + rep...)p Besides, Lemma 2.1 implies that d(c, c*) < 22r and d(p, (e), s 2ar. Putting everything together we have
d(c, (p)) < d(ê,c") + d(c ((c..." p) + d(p, (p)) < 2er + r 22r (1 + 4g)r
Besides, p E 0;-1 is equivalent to rep (p) E U, Therefore, E Ball(e", OPT) n 0 implies Tepar(P) (p) B 0 - and we have rep., (Ball(c", OPT) n 0.-1) C _ U- Thus,
(er S
Σ VEB
Wer (y) = wer B U,-1)
yεrep (Ball(er orT))o;-1)
which finishes the proof.
Utilizing Lemma 3.3 can now show that the weight of the final output of MAXCOVERAGE((,, with r 2 OPT is at least the number of points covered by any optimal solution.
Lemma 3.4 (Invariant for coverage weight). Let C* the set of centers of an optimal solution for k-center with z outliers on P., and let OPT be the radius of this solution. Let r OPT, where T E Then,
Ball(c", (PT)) n.P. S Wer (Ú CEEC.
U
(
B3 g
/=1
(recall that B3 Ball(cy, (3 8E)r) n Ner and war (B3 Ky Pt (ep H.
8

---

Proof. To prove the lemma, we show that for any i E [0, k]. there is a charging that satisfies the following conditions: 1) There is a set {ci ..i.....
of C C* and a function that charges each point in U Ba PPT n Pt to a point E U B og and 2) for any point y E U2=1 B at most (y) points from U (all(c), OPT) n Pt are mapped to y.
We prove this claim by induction induction hypothesis holds for i - 1. That is, there is a charging satisfying conditions and 2 for i 1. Then, we prove that these conditions hold for i.
The base case 0 trivially holds. Assume that i 2 and the
To define center c we consider two cases:
Case 1: there exists center C* C* \ , for which B hits the set of representa-
tives of Ball(c", OPT). That is, we have rep.,. (Bal(cc,, OPT)) n B + Ó. We then let of = c" We map every point of Ball(c", OPT) its unique representative. Case 2: the first case is not correct. Then, we let oj be any arbitrary point in C* (-11
In this case, we charge the uncharged points of OPPT B
We first consider Case 1. We charge each point p E Ball(c, OPT) to its representative rep (p). We next prove the following claim:
Claim. Let p E (all(c,, OPT). If Case 1 happens, then for every point g E P. that is charged to rep... (p), it holds that (c) (p).
Proof. For the sake of contradiction, assume that there is a point E Pt such that q is charged (p) and re) * (p). It means that at an iteration j < i, Case 2 happened and is charged to (P). Since Case 2 happened at iteration j. we have (Ball(c, OPT) n Byy = 0 and also & is charged to point in B2 Adding it to the assumption that is charged to (e) we have rep (p) E B B Besides, p E Ball(c, OPT) and therefore we have (p) reper (Ball(c) (B This implies that repe, (p) repll( OPP)) OPT)) B e which is a contradiction (Ball(,, OPT)) n B! eg,r 0.
The claim implies that for each point p E OPP)) at most (rep,ep.rp)) points are charged to (p). See Figure where the left blue ball represents Bry the right blue one indicates the area that points from rep,,. (Ball(c", OPT) can lie in, and the orange circle represents Ball(c", OPT). For each point p Ball(c". ,OPT), we have (p) E B3 Let q E Ball(c", OPT) be such that rep (q) (Ball(c,, OPT)) n Bl. The distance of c to any representative of a point E OPl)(" is
rep
rep (p)
4
Ball(a", OPT)
B rep (Ball(e" OPT))
Figure 2: Illustration of the claim's consequences.
d(c;, rep (p)) d(c;, rep, (4)) + d(rep (g). d(g, + d(c",p) d(p, rep. (p))
$ (1 + 45)r + 2er + 2OPT +2er & (3 +3+00 8e)r,
implying that (e) B
For Case 2: note that if E P. O then by definition of O we have rep & U--1 and hence (p) E B by definition of U--1. So. by induction hypothesis, p already charged to rep (p). Therefore, we only need to charge each point p E Ball(c", n O By Lemma 3.3 we have [Ball(c", OPT) n O.-1l S (e n U,-1). Also, only charged to

---

the points in U/ B which means that no point is charged a point in U,-1. Therefore, points in Ball(c", ,0PT) n 0 be charged to points in B! U1-1-
Lemma 3.5. Letr E R and OPT be the optimal radius for k-center clustering of Pt with 2 outliers. Then i 2 OPT, the value outliers Weight returned by MAXCOVERAGE(K, r) is at most 2.
Proof. Let C (cI,..., be the set of centers returned by MAXCOVERAGE((:;" r) and C* be the set of centers an optimal k-center clustering of Pt with z outliers. By the same reasoning as the proof of Lemma 3.2 it is
oulliers Weight = Wer (
Besides, Lemma 3.4 states that Wer (U B 2 Ec Ball(c", OPT) Pt). Moreover, C" the centers of optimal solution, Uo+Ec Ball(e", OPT) P. z. Putting everything together, we have
outliers Weight Σ n - Wer(U, B (.r) S n -eeec- Ba n S
=
which finishes the proof.
Lemma 3.2 and Lemma 3.5 together imply that the solution returned by Algorithm i feasible. Further, be shown that the level á at which FINDCENTERS(S: 2) becomes successful, fulfills è S r*. Together, this implies the following statement.
Lemma 3.6 (Approximation guarantee). Let OPT > 0 be the optimal radius for the k-center clustering of Pt with outliers, and let r* be the minimum number in R such that z² OPT. Then FINDCENTERS (, 2) returns a (3 p0pp)-appoo solution for k-center clustering problem with outliers, where p OPT
For p defined in Lemma 3.6 p holds according to the definition of R. immediately leads to a (6 + -(p)))approximatt
a algorithm. Next in Lemma 3.7 we show how to get S (1 + s), which
improves the approximation ratio of our algorithm to 3 3 (z). The idea is to rum parallel instances of our data structure with different values for parameter 3, so that always OPT < < (1+++)) =)OPT holds for r R in one of the instances.
Lemma 3.7 (Optimizing the approximation ratio), Let OPT O, and let > O be fixed. We define m : [1/logg (1 + E)]. Suppose we have m. parallel instances of data structure with parameter 22/mm-1 for the i-th instance. Then in at least one of the instances, we find (3 + (s))- approximation solution for k-center clustering with 2 outliers by calling FINDCENTERS(K:.2 2)-
The procedure MAXCOVERAGE(1: r) needs to temporarily edit the heap Hp.. This can be done by working on copy of the heap, as indicated in line The following result describes how this can be done faster, without actually copying the heap. The idea is to work in place and roll back all changes in the end. The formal proof is given in the full version.
Lemma 3.8 (Imitating of copying H.). Let u be the number of times that MAXCOVER (KE(K, r) updates heap H. Then copying heap H, in Line well all these u updates, can be handled in total time O l).
By using Lemma 3.8 and Lemma 2.2 we get the query time in Lemma 3.9
Lemma 3.9 (Query time). Let l and be two given parameters. Then FINDCENTERS( 2) described in Algorithm I has a time complexity of ((dim) -2 log log log A.
4 Conlusion
We developed a data structure for the fully dynamic k-center with outliers problem in metries of bounded doubling dimension. As compared to other works, the algorithm exhibits an improved query time while achieving the currently best-known approximation ratio of 3 + The query time optimal with respect to the dependency on k. Although the exponential dependency on the doubling actually not clear if this could improved
dimension in the running times seems necessary, to tackle even wider classes of metric spaces. This would be an interesting aspect for future work. However, Chan al. show that an amortized running time of (2z)) would be needed in general metric spaces.
10

---

Acknowledgements
The authors would like to thank the anonymous reviewers for their insightful comments. Annika Hennes' and Melanie Schmidt's s research was funded by the Deutsche Forschungsgemeinschfff (DFG, German Research Foundation) project number 456558332.
References
[1] MosanmadHossein 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 Annual ACM-SIAM Sym- posium on Discrete Algorithms (SODA), pages 2677-2727 Society for Industrial and Applied Mathematics, 2023.
[2] Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non- non-uniform k- center problem. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 55 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 67, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016.
[3] T-H. Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dynamic k-center clustering, In Proceedings of the 2018 World Wide Web Conference, pages 579-587, 2018.
[4] T-H. Hubert Chan, Silvio Lattanzi, Mauro Sozio, and Bo Wang. Fully dynamic k-center clustering with outliers. In Computing and Combinatories: 28th International Conference, COCOON 2022, Shenzhen, China, October 22-24, 2022, Proceedings, pages 150-161. Springer, 2023.
[5] 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 626 635,635,15 1997.
[6] 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 Anmual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA, pages 64.-651. ACM/SIAM, 2001.
[7] Mark de Berg. Leyla Biabani, and Morteza Monemizadeh. k-center clustering with outliers in the MPC and streaming model. CoRR, abs/2302.12811 2023.
[8] Hendrik Fichtenberger. Monika Henzinger, and Andreas Wiese. On fully dynamic constant- factor approximation algorithms for clustering problems. CoRR, abs/21 2021.
[9] Teofilo F Gonzalez. Clustering minimize the maximum intercluster distance. Theoretical computer science, 38:293-306, 1985.
[10] 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.
[11] Anupam Gupta, Robert Krauthgamer, and James R Lee. Bounded geometries, fractals, and now-distortion embeddings. In Proceedings of the 44th Annual IEEE Symposium Foundations of Computer Science, 2003, pages 534 543. IEEE, 2003.
[12] Juha Heinonen. Lectures analysis on metric spaces. Springer Science & Business Media, 2001.
[13] 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.
[14] Wen-Lian Hsu and George I.. Nemhauser. Easy and hard bottleneck location problems. Discrete Applied Mathematics, 1(3):209-215, 1979.

---

[15] Robert Krauthgamer and James R Lee. Navigating nets: Simple algorithms for proximity search. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 798-807. Citeseer, 2004.
[16] Stuart P. Lloyd. Least squares quantization in PCM. IEEE Transactions Information Theory, 28(2): 1att1129,7,, 1982. Originally published in 1957 as Bell Laboratories Technical Memorandum.
[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. Fully dynamic clustering and diversity maximization in doubling metrics. CoRR, abs/2302.07771, 2023.
[19] Melanie Schmidt and Christian Sohler. Fully dynamic hierarchical diameter k-clustering and k-center. arXiv preprint arXiv: /9X0v:9900..0 02645, 2019.
12

---

A Maintaining the data structure
As we explained in Section 2 our data structure consists of O(log A) levels : (0) 2 l E Z, 0 S log, A] + T. where < 3 < 1 is given parameter. Similar to Krauthgamer and Lee [15), on each level r, we maintain net N,, which is r-net of N,/2. In this section, we explain how to maintain our data structure after each insert/delete update, and analyze the update time.
For every point p E Nr, maintain the of all its parents and all its children. We start by bounding the number of children and parents of each point. Recall that E N, is called parent of E Ne/2 if d(p.g) q) I r. We first show that the number of children for each point of size 20(di))
Lemma A.1 (Number of children). Let p E N,- The number of children of p is most 22m
Proof. For every child N1/2 of p it d(p, g) S Therefore, the set of children is covered by Ball(p, r). Using the definition of doubling dimension twice, it follows that the set of children can be covered by 2 dim balls of radius r/4. As any two points in N, have distance at least r/2, the claim follows.
Then, in similar fashion, we can deduce the number of parents. Lemma A.2 (Number of parents). Let p Ny. The number of parents of p is bounded by 20(dim)
A.1 Finding the neighbours
In this section, we explain FindNeighbours which takes as input value 2 2 and point E Po and returns for every R \ {0} the set of neighbors of p within distance yr. Later, we use this procedure to maintain our data structure after insertions and deletions.
Procedure FINDNEIGHBOURS(p. ?)
Tmax := 3 2ogg A1
Tmax
3 S, + Nr
while > do
r r/r/2
S, S-+0
for all s E S2r do
for all children q E N, of do
if ddpp.)) 9) < ...7.. then
10
S, + S, [q}
return S3, S2g. S4s, Sgg, .... Srmax
Lemma A.3. Let P P. and 7 2 2. Then, for all r R. \ {0}. set S, that compute in FindNeighbours (p, 7) consists of all elements in N, within distance r of
Proof. We show the statement via induction on r. For = Tmax B 2oog A1, line implies S, N, and therefore the statement is trivially fulfilled. Now assume the statement holds for 2r, where r < Tmax- Consider x E N, such that d(p. < yr. Then, d(p, (x)) < d(p, x) (x)) S yr + 2r < 2yr, hence, by induction hypothesis, rep,,, (x) E S2.- This means, child of element in S2r, and the condition of the for loop in line 8 holds. As further d(p, x) - yr by assumption, r added to S, line 10
Next, we bound the size of S, Lemma A.4
Lemma A.4. Let R. Then, S, computed in FindNeighbours p. is of size dimm2
Proof. The condition in Line of FindNeighbourss implies that any point S, is within distance r of p. Hence, S, is covered by Balle, 7 rr. Besides, S, S N,, which means that the distance between any two points in S, is more than By applying the definition of doubling dimension, it
13

---

follows that Ball(p, Y r) can be covered by - 20(dim) balls of radius r r/2. Adding it to S, S N, implies that each of these balls of radius r/2 contains most one point from S,.. Therefore. S, is of size 7 dim 20(dim).
Lemma A.5. Let p E P and y 2 be given. Then, the procedure FindNeighbours/ p. 7) runs in time 20(dim) yddim log A.
Proof. The while loop in Line iterates backward through all the Ollog A) levels. On every level. all children of all E S2, are examined. By Lemma A.4 [Sarl E (dimm0(ddm) and by Lemma A.1 every 8 E |Sar| has 22m children. Multiplying these terms yields the claim.
A.2 Insertion
In this section, we show how to maintain our data structure after the insertion of point p. As described in A we start by calling FallingFindNNighhoours, which goes through the levels from top bottom (high to low) and recursively computes set S, for each level r. Lemma A.3 implies that for any point q E Ny. d(p. q) S r. then S, contains q. This guarantees that later we can find all parents and children of using these S, sets. Next, we go through the levels from bottom to top to find the lowest level f, which we can find a representative for p. or in other words, there is Q N₂ within distance f of p. Then, we add p to all levels lower than f. For levels r >> i, we do not need to add p to N, because there already a point in level r that can represent p by the definition of We determine this representative recursively according to rep, Finally, we increase the weight for the respective representative of p in each level by one.
Algorithm 2: INSERT(P)
Tmax 3 2 20108,
2 S3, S28, S4,, Sag, S mas
FindNeighbours
// finding the lowest level
that have representative for P
r < 3, f x 2rmax while r < Tmax do if' there is a point s E S, such that d(p, s) S then
8 rtr
rep,(p) 5 for all $ E S, such that d(p, s) S r do
10
Save as parent of and save child of
11
break
12
r +- 2r
// adding p to levels lover than
14 for all r R such that < f do
N₂ < N2 {p}
16 Save E N, as a parent of N,y2 and save E Ne/2 as a of N,
17
(p) +
18
UPDXTENLIGHBOURRHODAADI
// finding the representative p in all levels upper than
20 r < 2F
while mmax do
22
(p), +- rep, (rep,
23 r 2r
24 // updating the weight function for all r E R do
26 L w, (rep, +- (reer,, +
After inserting the point p to Ner, we need to compute Ppr and B Besides, for any point q E B1 (g B3 similarly), we need to add p to B) (B3 similarly). We perform this operation
14

---

Procedure U f): procedure to update neighbourhoods after adding p all levels below N₁
Tmax == 3 2222 A]
Tg, T23, Ta3, Tss.... ..... T Trman FindNeighbours/ (3 8E)/E)
3 // updating neighborhoods B- and B"
for all r' E R such that r' < 8 and rE/e S Tmax do
r := r==r'/e r'/E
> r'
B + 0, B +
for all E T," do
By, f- B3 U {q}. Byrr + B qu {p}
D d(p,g) S (3 8e)r
d(ppp.) q) S (1 4:)r then
B,,- B.r U4g B B U {p}
in Procedure Updaat-Neighbouuhoodddd In Lemma A.6 analyze the correctness and update time of this procedure.
Lemma A.6. Let p be point to be inserted and i as in the algorithm after execution of the while loop in Line 5 Then, SPPATTENEIGHROURHOODAAAA finds B,, p.r and B3 for any r E R. such that er < f. Besides, the total update time of this procedure is 20(dmm) dim log A.
p, f) that we invoke in Line [8 Algorithm 2
Proof. By Lemma A.3 T, contains all points of N, within distance (3 + 8s)r Then if we define r := r' /e, holds that T,, contains all points of Ner within distance (3)r (3 + 88)r of p. This means that we can find B3 by exploring Tr,, which we do in Line of the procedure. By restricting points q in Tr such that d(p, 9) I (1 + 4z)r, we find all the points that belong to B
We next discuss the running time. Lemma A.5 states that the running time of FindNeiiht bours p, + 8s)/E) is 20(dim)g- dim log A. Then, we iterate over Tp- for at most O(log A) values of r', which takes O(Ir,() for each iteration. Lemma A.4 shows that Thr is of size 20(dim) dim Therefore, the total running time of these O(log A) iterations is also 20(dim) dim log A, which finishes the proof.
((3 + 3 (dim)
Updating the heaps. To avoid redundancy, we do not include updating Heaps H, in the pseu- docodes. However, it can be easily handled. Note that neighborhoods B and B are balls of the same size. Therefore, y E B, is equivalent to B) Hence, whenever the weight of point in N, is changed, it is enough to update the weight of all points in B1, and their corresponding element in heap H, The size of B1, 20(dim) dim by Lemma 2.2] and we can do each heap update in Olog n) time. Therefore, extra 20(dmm) dim log factor will be multiplied by the running time of Algorithm due to maintaining the heaps.
Lemma A.7. Let n be the size of point set P.. Then after insertion of any point to Pt. we can update our data structure in time 20(dim) g-2 -2dm log log
Proof. As we discussed above, 20(dmm) dim log factor will be multiplied by the running time of Algorithm due to maintaining the heaps. Therefore, is enough to show that the running time of Algorithm is 20dimm dim log A.
In Algorithm
2 we first call FindNeighbours p. 2). which takes 20(dmm) log A according to Lemma A.5 To find F, we next iterate over S, for at most Oloog A) values of r. Then, we add p to all levels lower than f. which takes time log A. We next invoke Uppaateeiighhouroodddddo
(,, r), which done in time 20(dim) dim log A according to Lemma A.6 This takes 20(am) log A, since S, is of size 20 (dim) by Lemma A.4 Finally, we update the representatives of and their weights, which is done in time Olog A). Putting everything together proves that the running time of Algorithm 2 (ddmm) dim log A, which finishes the proof.
15

---

A.3 Deletion
In this section, we explain how to maintain our data structure after the deletion of point p. As described in Algorithm{]] we first produce sets S, and T, for all E R that are used for updating parents and children as well as neighborhoods. We then iterate over the levels r R from bottom to top. During the algorithm, we may elevate some points from N2/2 Nr to N, to maintain our data structure. We refer to the set of these points that are elevated to Nr as Fr,. After changing the representative of a point, we need to change the weights of its previous representative in the next level as well as the indirect previous representatives in the upper levels. To make this process of updating weights efficient, we define the set D, and a function 6, D, - E for each r E R. The set D, refers to the set of points & E N, whose weight should be updated by the value 8.[9]]
After deleting p. we need to find new representative for any point q E Nr/2 and also reduce / (2() from its previous indirect representatives in the upper levels. To do this, we decrease 82. [rep (p) by (9)) After deleting p from N,, any point g E N,,/ that was represented by p in N, would not have any representative. Besides, we need to find a representative in N, for the points in E, Let q E Ney2 be a point such that rep, = or E E To find a new representative for q in N,, we consider two cases: either y has a parent in N, \ {p) or p is the only parent of q in N,.
For the first case, we choose parent E NN, {p} of q its representative in N,. Then, we increase wy (x) and (x]] by "r/2(9) to update the weight of all points that represent q in higher levels directly or indirectly. For the second case, we have to elevate to Nr. After elevating 9 to Nr. we need to find its parents and children. To find the children, it enough to explore Sp/2- is because if
Nr/2 is child of q E N,. then d(g, 8) r. Adding it d(p, q) S r, we have d(p, s) < 2r = 4rr/2) by triangle inequality. Therefore, E Sr/2 and it is enough explore S,/2- With a similar argument, it is enough to explore S2r to find the parents of q in N2r-
We next call UpplateNeighouurooooHevvaa can compute B and B 4.r/e by exploring Tp.
r, T,). In Lemma A.9
we show that this procedure
At the end of each iteration, we call UDDXTENNEGHHOUURHOOORRRAWW p. r). This procedure deletes p from all the neighborhoods of level r that contain p. Note that for E (1,3), p E B and E B are equivalent. Hence, it enough to iterate over all E B and delete p from B for i (1,3].
To show that [[plateeeigbbouroooddoooo prove Lemma A.8] which is about the distance of the points in E, to p.
computes the neighborhoods in Lemma A.9
we first
Lemma A.8. Let r E R, and let E,, be the set of elevated points in Algorithm 3 Then, for any point qE E E we have d(p, q) Sr.
Proof. Let â be the smallest level in R such that q is elevated to it. It means that q is child of p E N,, and therefore, d(p, 4) S f. Besides, we have i S r, which implies d(p, q) S r.
We next call [[DAXEENEHHBUURHOODELLLLEE to create B,,, and B3 g,r as well as add q to the neighborhoods in level F' that must contain q.
Lemma A.9. Let r' E R. & E. and T as constructed in Line 3 of Algorithm 3 We define qqr" TT.) computes By,r and B and
r : l/e. The procedure UydlueNeghhuurooooleeee updates the neighborhoods B².r (and B2,,) for all o' B1 qa (4' E BBar) by adding q to them. Besides, this procedure runs in time O( dlmm)(
Proof. Let p be the point to be deleted when calling Algorithm q E E,, implies that either was the representative of q in Nr., or q E E /2. If was the representative of q in Np,, have d(p. q) < r'. Otherwise, if q E E,,/2. Lemma A.8 states that d(p, q) < r'/2 < r'. Therefore, d(p,q) < alwwys holds. By Lemma A.3 T, contains all points x E N, such that dip, x)) < (1 + (3+88) 8E)/e)r' = r' + (3 + 8e)r, for r r'/e. Let o' E N,, be a point such that d(g, q') (3 + 8s)r. We claim that we add g' to B3 To do this, it is enough to show that o' E Tr. As we mentioned, d(p.g) < <r d(g.g') < (3 85)r. Then by the triangle inequality we have d(p,d') S q().g) + d(g. S'' (3 (3+ 8B)r, which means that q' E T, and it is enough to explore T, for computing B3 Note that the same argument also works for B)
16

---

Algorithm 3: DELETE(P)
mmax := 2o,,, A1
2 Sg. S28, S49. Sag. ... Srmar
FindNeighbours. p: 4)
3 Ts. T23, T13. Tss, T maa
FindNeighbours, 1 (3+ 8E)/E
E3/2 0. Dg + 0. 8g
while S. Tmax do
E, 5
D2r + 0 82r f 0
// updating the weights the points the level wir (rep,(p)) <- (p)
10
11
for all q E D,
12
Wy (1)) +- Wr (y) + 8.(1) D2r,02r --UPDATEWEIGHTCCL
13
rep,, 6r(4)
// updating the level
15
for all E NNr/2 \ {p} that rep,(g) = and all q E Er// do if rep,, = p then
16
17
D2r, 62r UPDATEWWIIHHT 82,, rep -2
18
zepresentative in N, for if q has parent x in N, {p} then
// finding
19
20
rep, (g) +
21
(x)x f- w. (x) + (2/2(4)
22
D2r, 82r UUPDATEWEIGHT re. (e), Wy 12(1)
23
else
24
// adding to N.
25
N, + (g), E, (g
26
(e), + w,(g) t wr/2(g)
27
if < then
28
S, S.
29
d(g p) < (1 (3 8E)/E) then T. + TT
30
31
// finding all children of g by exploring S.12
32
for all E S,12 do
33
if d(q, s) S then Save q parent of and child of p
// finding for all s E S2, do if dd(, 8) < 2r then
parents of a Nar by exploring Sar
36
38
Save s as parent of g, and q as a child of
39
UpddteeNeighourhooodeeeaaa g. T,)
N. < N₂ {p)
41
r+ 2r
UPPAAEEEEGIDDURROOORRRVYYYY.
43
Delete all the data (such as parents, children, weight, and representative) corresponding to
17

---

Further, B (and ),.r) contains all points whose neighborhoods need to be updated to include
The procedure iterates through all Ty,, so the running time is O[Tr,] O( (dim)) C
Procedure UPDATEWFIGHT( 6, w)
if q $ D then
D + D {q}
8lg] < 0
5(d) < 8[g] + w
return C
Procedure UUDAAINNEECHOOUUHHODLLLELVAVA r', T,)): a procedure to update neighbour- hoods after adding q Np
r := r//E
> r' = er
if B 2.2 Al then
return
q.r + 0, B -
5 for all of E T do
if d(gg.00 q') ) s (3 + 8E)r then
9.r + g.r U {g). B t B3 U {p}
if (d(g.g/ d') s (1 45)r then
B 4r f By, (d'), ByGr + By,r u{}
Procedure (PPATZENECCHHOURRROORRRRMYYYY,,, r'): a procedure to update neighbourhoods after removing p from N,
r := r//E
=er
if r 2 2(102 Al or p $ N, then
L return
for all E B3
ppr do
L B3, <- B3 qir (p)
for all q B1 p.r do
L B & B ur {p)
8 Delete B and Brr
p.r
To prove the update time of Algorithm we first prove Lemma A.10 and Lemma A.1I
Lemma A.10. Let r E Then, the set E,, Algorithm 3 is of size 20(dim)
Proof. Lemma A.8 states that d(p. 4) S r holds for any q E,. Moreover, E, S N,. which implies that the distance between any two points in E, is more than r by the definition N,. Therefore, the definition of doubling dimension implies that |, s 20(im))
Lemma A.11. Let r E R. Then the set D, in Algorithm 3 is of size 20dim)
Proof. To prove the lemma, we first claim that for any r E R. if E D,, then d(p, y) < 2r. We prove the claim by induction on r. For the base case, we consider = 3. Since D3 0. claim trivially holds for
B. Now, we show that also holds for 2r. Let v be point in D2r- Then, is added to D2r in one of the Lines [3
claim holds for r R, then
17 or 22 of Algorithm 3 that (q). By the induction hypothesis, we have d(p, q) < 2r. Besides, we know that
added in Line [3] means that there point q E D., such
18

---

d(g. v) d(g, re. (g) < 2r. Hence, d(p, v) 4r 2(2r) holds by the triangle inequality. If u is added D2- in Line 17 we have v = (P), and we know that rep,, re)2 I 2r. Therefore. d(p, m) = d(, 2r (P) I 2r < 2(2r). Finally, we consider the case that v is added to D2r in Line 22 In this case, v = rep2. (x) for a point x E N,, and x rep,-() for a point Q E N2 such that either y was child of p or q E E2 If q was child of p, then d(p; q) S r, and if q Br then d(p, g) S sr S r by Lemma A.8 Therefore, d(p, q) S r always holds. Besides, d(g. x)) as x is a parent of q. Moreover, we have d(z, rep2, (x)) S 2r. Putting everything together we have
d(p, v) = d(p, rep2, (x)) I d(p. q) + d(g, x) + d(x repa (x)) S +r + 2r = 2(2r)
Thus, our claim holds.
In addition, D. N,, which means that the distance between any two points in D, is more than r. Adding this to the claim, the definition of doubling dimension implies that D, is of size 20(dim). C
Now, we can discuss the update time for maintaining our data structure after each deletion.
Lemma A.12. Let n be the size of the point set P.. Then after deletion of any point from Pt, we can update our data structure in time 20(dim) dim log A log n..
Proof. As we discussed in Section A.2 2 to maintain the heaps, a (ddim)) dim log n factor will be multiplied by the running time of A Algorithm Hence, is enough show that the running time of Algorithm is 20(dim]
dia log A.
In Algorithm 3 we first call FindNeighbours for y = 4 and 7 = 1 + (3 + 8c)/s to find sets S, and T,. which take time 20(dim) log and 20(ammm dim log A, respectively, according to Lemma A.5
We next iterate over Ollog A) levels and in each level, we itcrate over some children of p and the elevated points Er/2, and then we call [wcccacceeegbbbuoooooReeoyooo
which takes O p.r [B)_-)) = g2 -id).. The number of p's children and the elevated points are 20(dim) by Lemma A.2 and Lemma A.10 respectively. Thus, iterate over 20(dim) points in each level, and in each iteration, all the operations other than (bw.aateeiiggbbooooooeeeeeeeeeee can be done in time 20ddim) Besides, the running time of [Lpaateeeighoourooodlleeeee is O([T>-)) ((20(dim) dim). Hence, the total running time of the iteration over the O(log A) levels is ((20d)))) dim log A).
Proof Lemma 2.3
Now, adding Lemma A.7 and Lemma which about the update time of our data structure.
finishes the proof of
Lemma 2.3
Let be the size of point set Pt. Then after insertion//leletion of any point to Pa, we can update our data structure in time (ddm)) dim log lognn. n.
Lemma 2.3
B Omitted Proofs
Lemma 2.1 Let E Pt and E R. Then d(p, rp), S 2r. In particular, d(p, (p))) S 2sr, where l'g for the error parameler e'.
Proof. Let r' E R. As N2r is a -re Further, by definition, rep2r (p) rep (rep, (p)) and hence, d(rep,, (p), rep (p)) < 2r'. Thus,
-net of Ny,, we know that (p) rep2. (rep,- (p))) I 2r'.
d(p, (e), S
Σ d(rep, rep (p) < Σ r' 28 P'e PER
Σ 2 232 $ = (1)
r'er: YER
<<log
For r' = Er, we make a case distinction. er 2 33 then er E R and hence d(p. rep.
) < 22r by
Equation er B, then rep,reper (p)) = 0 2er because reper(p) = by definition. n
Lemma 2.2 Let e R and p Ner. The sets By and B3, defined above are of size at most In particular, the size is O -dm) d for constant doubling dimension dim.
g0ldim)
19

---

Proof. By recursively applying the definition of doubling dimension i ttmess, we can cover ball of radius (3 + 8c)r with most 2 dim balls of radius (3+Se)r For i [log 3+
e/2 1 it follows that B
can be covered by (2 3+88 ) E gdim balls of radius er As Bp,- S Ner. the distance between 2 any pair of points in B3 is at least er. Therefore, each of the -b-bals contains most one point, which finishes the proof.
220ciim)
c/2
Lemma 3.1
Let is be an integer, 0 S kc and R. After the i-th iteration of the loop in Line 3 Uu is the total weight of unmarked points in B for each E Ner- More formally, Hy = (er(B,)
By,, y.r nU,) for any E Ner after the i-th iteration.
Proof. Let H; denote the state of the heap and M the set Marked at the end of iteration i, and HO and M denote the respective sets before entering the for-loop. It can easily be seen that M Ujs: for every i S k by a simple induction. Initially, M = 0 = Uf s.. Now assume M Uj B3 for some i < k. Noting that M is only updated in line 7 of MAXCOVERAGE(K; r). Lines 6 and imply that all points from B²,,- that are not in M yet are added to M Therefore, M² = M B3 e., = Uss: Recall that U3 = Nar \ U ej. ey.r. This directly implies that U; corresponds to the set of points that are still unmarked at the end of iteration i, that is U;- Ner MM. From this, it also immediately follows that U3 U:-1 B
Now we can show [||=]] Wer Wer( n U2) for all < k. For i O, the heap is not modified and no points are covered yet, i.e. H [c] Wer (B2, and Un = Ner- Now assume Hi- =
Wer [B) p.r n 11 for some i < k. Lines to in MAXCOVERAGE(KK r) are equivalent to
Y B our \ \M--'Vx E B decrease H, by (er
Neighborhood membership is a symmetric relation in the following sense. If a E Ner is contained within the local neighborhood of y E Ner, then the converse is also true: For every v, Nor such that x E By, r also holds y E Bryr. Therefore, Equation (2) is equivalent to
Vx E Ner Vy E B3 o.r
0 OB2 2,r M decrease H,[ by Wer (J)
which means that during iteration i, the heap value of x E Ner is reduced by wer Be,nBBi x. \M--).. Because of the equality Fu,r n B! (M--1 = B n B n U--1, we can deduce
HM[a] = H [x]] - Wer (B o n nB, a. nU:-1) = wer (B), 2.r n NU:11) - Wer (B ogr
n 2. IU;1)
(3) Wer (B,, nU,-1 (B3 our n (u wer (B n nu \ B B2.r)
= -B,, nU,)
where (3) follows from the fact that W (X (Y) -x) for Y C
Lemma 3.6 Let OPT > 0 be the optimal radius for the k-center clustering of Pt with outliers, and let r* be the minimum number in R such that r* 2 ОPT. Then FINDCENTERS(K, 2) returns (3 + 10=) papproiatt solution for k-center clustering problem with outliers, where p OPT.
Proof. We first show that i < r. To do this, we consider cases: f 2 F S 2. For the first case, it holds that the outliers Weight returned by MAXCOVERAGE (k, f/2) is more than and then we can conduct that OPT f/2. It is because otherwise, MAXCOVERAGE((; f/2). outliers Weight would be less than 2 by Lemma 3.5 which is a contradiction. It means that r- > f/2, and then r we have r" 2 f. Now we consider the second case that 2. Since OPT: > O, we have OPT 2 d = 2. Adding it to OPT < r", which is an assumption of this lemma, we have < < OPT <r" Thus f I r* holds in both cases.
according to the definition of Rt and
Due to Lemma 3.2 and Lemma MAXCOVERAGE(K:)) f) returned by FINDCENTERS(K; =) is a set of k centers such that all but most points in P. are within distance (3 10e) f of these centers. (3+10e)
Hence, FINDCENTERS(K; 2) returns a therefore, the approximation ratio is at most (3 + 10=)p, where OPT.
OPT -aprroximation solution. We also showed that f < r".
20

---

Let OPT > O, and let > O be fixed. We define m == [1/ (1 + E)}. Suppose we have m parallel instances of our data structure with parameter 3 = 22/m-1 for the i-th instance. Then in at least one of the instances, we find (3 + Ole))-aaproximatiin solution for k-center clustering with outliers by calling FINDCENTERS(;: 2).
Lemma 3.7
Proof. Since assume OPT > O, then we have OPT 2 dnmi =2 Let 5" E [1, [og Al] be such that 2 < OPT S 2",, and let i" E [1, m] be such that 2 21--1+("--
OPT I have 3/22 =2'" /m R. Therefore by Lemma 3.6 FINDCENTERS(K, 2) returns a (3 (3+ 10=)p" -aprrxximaaooonn solution, where p- 23" 20"-145 /m /OPT. To finish the proof of Lemma, we show that p < (1+ 8), which immediately implies a (3 + ((e)) apprroxmatoi solution. According the definition of i we have 21/m, Besides, m 2 1/ log, (1 + E) holds by the definition for of m, which means 1/m S log, (1 + s). Therefore, 21/m (1 E), and then we have p² 21/m < (1 + E), which finishes the proof.
2 "d-1"""/m /m_ For the instance with parameter / 2 /m-1,
p" 2/- -1+1-11"//0 /m /OPT 2 -1+ /m /2/ -1-(1111))0))0
Let u be the number of times that MAXCOVERAGE(K::) r) updates heap H. Then copying heap H, in Line 2 as well as all these updates, can be handled in total time O(u log
Lemma 3.8
Proof. Procedure MAXCOVERAGE((:: r) sets as a copy of Hy, and then it decreases the value of some keys in H during the algorithm. Note that it never inserts deletes new key to H. and the only possible update is decreasing the value of a key. We claim that it not necessary to really copy the heap H, which takes ((HH, O()) time. Instead, we apply all the updates on H, and then undo them at the end of MAXCOVERAGE(E; r). Although the procedure can change H, as we defined, we guarantee that H, is the same at the start and end of the procedure. To do this, we keep a record of all u updates, and at end of MAXCOVERACE COOVERAGE(K. (k. r). we undo all these u updates, which means increasing the value of each updated key with the decreased value. Since the number of updates is u, then we can do all the reverse updates in (u log H OO logn).
Lemma 3.9
Let k and z be two given parameters. Then FINDCENTERS(K: 2) described in Algo- rithm 1 has time complexity of 20(im)) g log n log log A.
Proof. FINDCENTERS(K; =) perform a binary-search on R and in each search, it invokes MAXCOVER AGE two times. Therefore, MAXCOVERAGE is called O(log Rt)) times in total, which is Oloo log A) as [R] = Olog A). Hence, it remains to show that the running time of MAXCOVERAGE(K; r) is 20 2 & logn.
Now, we discuss the running time of MAXCOVERAGE(K; r). This procedure consists of iterations,
in which iterate all elements y E B Recall that Lemma 2.2 states B3 is of size at most
g0(dim) adii
Then for any y. we iterate on all elements E B and update H[x]] in Line Again by
Lemma 2.2 the size of B! is most 20(dim))
(dian)
edim Therefore, we update heap H most
times. Then by Lemma 3.8 these heap updates and also copying heap H, in Line 2 are done in total
time of 20(dim) g -2 klo n.
Proof of Theorem 1.1
Theorem 1.1 Let (M, d) be a metric space of bounded doubling dimension dim, and let E >> 0 be an error parameter. There exists a deterministic dynamic algorithm that allows the insertion or deletion of points from M using worst-case & -O(dim) log n log A update time. Moreover, at any time t, it can be queried by parameters i and compute (3 + e) appprxximaae solution for the k-center problem with outliers of Pt using worst-case e- --(ddim) k log n log log A query time, where Pt is the set of points that are inserted but not deleted up to time I, and n is the size of P..
instances of our data structure with parameter 3 = 2//m- for the i-th instance. We first discuss the approximation ratio. If OPT > 0, then we find a (3 + (()) -aprr)--ppxoiiattio solution by Lemma 3.7 Otherwise if OPT = 0. then by Lemma the outliers Weight returned by MAXCOVER MAXCOVERAGE(C 0) at most z. In this case, we return a solution with radius 0 in Line which is an exact solution.
Proof. We maintain m [1/
21

---

Now we discuss the update time. If we maintain m ( log(1++)) instances of our data structure in parallel, it incurs an ([1/log(1 + =)) = ()= factor the time complexity. In each instance. the update time per insert/delete g be computed in time O(2Ordim) - log n log log A) by Lemma 3.9 Therefore,
log A log n by Lemma 2.3 and the l centers can handle each
insert/delete in 20(di)) e (2 +1) log A log g e-O(dim) log n log A total time and we can find the centers in (20(dim)) g - (2dim)+1 k log n log log A) = = -O(dim) k log n log log A total time. E
22


Reviews:
[{"review_id": "q68fuei55t", "reviewer": "Reviewer_k1og", "summary": "This paper consider the $k$-center problem with outliers in the fully dynamic setting (insertions and deletions of points).\n\nThe assumption is that the metric space has bounded doubling dimension (as a side note: some assumption is necessary to get better bounds due to known lower bounds).\n\nThe main result of the paper is to give an algorithm with the following guarantees:\n\n- Worst-case  update time  exp(double-dimension) log n log (Delta)\n- Worst-case query time: exp(double-dimension)  k log n log log Delta\n\nNote that the query time is almost optimal in the sense that $k$ is needed to return $k$ centers.  Independent concurrent work has achieved similar guarantees. In particular, [16] uses similar ideas but pay an k^2 in query time. \nThe idea of this paper and [16] is to use \"Navigating sets\" as previously used. Now an issue is that they don't work off the shelves for the outlier settings. [16] solves this by showing that a certain level forms a coarset and then runs the 3-approximation algorithm Charikar et al. To run this algorithm from scratch incurs a running time overhead. Instead the current paper includes smart information in their datastructrue that avoids running this algorithm from scratch leading to the better running time.", "questions": "- What factors in your running times are necessary? Is the exponential dependency on doubling dimension necessary etc?\n\nMinor things: \n\n- line 37 \"which gives\"\n\n- Thm 1.1. shouldn't it be insertions and deletions instead of insertions or deletions?\n\n\n\n", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- An improvement on a natural problem k-center with outliers in the dynamic setting.\n\n- Close to optimal query time (is the exponential dependency on doubling dimension necessary?)\n\n- Smart algorithmic techniques.", "weaknesses": "- Quite a complex algorithm in the end.\n\n- The improvement is quite specialized: query time for the case of double dimensions. Yes, I know that some restrictions on the input is necessary so cannot complain too much but I do think this decreases the general appeal of the paper.\n\n- Would 2-approximation be possible? This is interesting as the best \"combinatorial\" approximation algorithm for k-center with outliers is 3...\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Question:** What factors in your running times are necessary? Is the exponential dependency on doubling dimension necessary etc?\n\n**Response:** These are interesting questions. The exponential dependency on the doubling dimension seems unavoidable. We will pose this question as an open problem for future work. In general, it would be interesting to devise a lower bound for the query time complexity of dynamic algorithms for this problem.\n\nWe should mention that there is a lower bound on the storage needed for obtaining $(1+\\epsilon)$-approximations in the streaming model via coresets proven by De Berg et al [7] (below). In particular, they show that any dynamic deterministic algorithm for this problem needs storage of $\\Omega( (k/\\epsilon^{\\text{dim}})\\log{\\Delta} + z )$. That is, an exponential dependency on doubling dimension and a logarithmic dependency on the aspect ratio ($\\Delta$) in the storage of any streaming algorithm is necessary. However, the streaming setting is incomparable to the dynamic model and it is not clear if a space requirement of a streaming algorithm can be transferred to the query time requirement of a dynamic algorithm. In fact, the streaming algorithm needs $\\Omega(z)$ bound in the space, but we do not have such a term in the query time of our dynamic algorithm.\n\n**Reference:**\n[7] Mark de Berg, Leyla Biabani, Morteza Monemizadeh: k-Center Clustering with Outliers in the MPC and Streaming Model. IPDPS 2023 "}, {"review_id": "lDMeetCVNb", "reviewer": "Reviewer_bgty", "summary": "In k-center with z outliers problem, the input is a data set X that lies in metric space and the goal is to find a center set C of size k such that the z+1 largest distance from points in X to C is minimized. This paper stuided a dynamic version of this paper where data point can be inserted and deleted but we should output an approximate solution to the problem at any time.\n\nThe main result of this paper is $3+\\epsilon$ approximation dynamic algorithm that supports an $\\epsilon^{-O(\\mathrm{ddim})}\\log n \\log \\Delta$ update time and an $\\epsilon^{-O(\\mathrm{ddim})}k\\log n \\log \\log \\Delta$ where $\\mathrm{ddim}$ is the doubling dimension of metric space, $n=|X|$, and $\\Delta$ is the ratio between the maximum and minimum pariwise distance of $X$.\n\nThis result does not significantly improve previous results. For example, [16] already gave a dynamic algorithm with an $\\epsilon^{-O(\\mathrm{ddim})}\\log \\Delta$ update time, an $\\epsilon^{-O(\\mathrm{ddim})}(k+z)^2\\log \\Delta$ query time, and the same approximation ratio. The new algorithm only trade a $poly(k+z)$ factor with an $\\log n$ in the query time. Authors claimed the work is finished indepdently from [16] while even comparing with a weaker and ealier result [7], the new bounds do not seem to be very strong. \n\nMoreover, I do not see the main technical contributions of this paper after reading the first few pages. Authors introduce a few existing techniques of other papers but skip to technical parts directly. I suggest to add a section named \"Technical Contribution\" to feed the readers with spoons. ", "questions": "1. The algorithm seems to build on a few existing techniques and the main technical contributions of this paper are not very clear to me. Can you summary your main technical contributions?", "limitations": "I do not see potential negative societal impact.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. A new algorithm for robust dynamic k-center in doubling metric space.", "weaknesses": "1. The algorithm only achieves similar guarantee, comparing with existing results.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n**Comment:** This result does not significantly improve previous results. For example, [16] already gave a dynamic algorithm with an $\\epsilon^{-O(\\text{ddim})} \\log{\\Delta}$ update time, an $\\epsilon^{-O(\\text{ddim})} (k+z)^2 \\log{\\Delta}$ query time, and the same approximation ratio. The new algorithm only trade a $poly(k+z)$ factor with an $\\log{n}$ in the query time. Authors claimed the work is finished independently from [16] while even comparing with a weaker and earlier result [7], the new bounds do not seem to be very strong. \n\n**Response:** Interestingly, if we assume that the $n$ input points are distinct, then $\\Delta \\geq n^{1/\\text{ddim}}$, so $\\log{n} \\leq \\text{ddim}\\cdot\\log{\\Delta}$. Thus, our query time can also be bounded by $ O(\\epsilon^{-\\text{ddim}} k \\log{\\Delta} \\log\\log{\\Delta})$ for constant $\\text{ddim}$ while the running time of [16] is $O(\\epsilon^{-\\text{ddim}}(k+z)^2 \\log{\\Delta})$. Thus, we are replacing a $(k+z)^2$ by a $k\\cdot\\log\\log{\\Delta}$ factor. Now, we consider the following regimes: \n1. $k$ and $z$ are constants: For this case, our query time and the query time in [16] are comparable, [16] is slightly better by a $\\log\n\\log \\Delta$ factor.\n2. If either $k$ or $z$ is mildly dependent on $n$, our query time is significantly better than the query time in [16]. In fact, already for $k \\in O(\\log{n})$ and $z\\in \\Omega(\\sqrt{n})$, the query complexity of [16] would be linear in $n$ compared to the poly-logarithmic dependency in terms of $n$ for our query time.\n3. More interestingly, for a realistic regime where $z$ is an $\\epsilon$-fraction of $n$, the query time of the dynamic algorithm presented in [16] has quadratic dependency ($n^2$) in terms of $n$ while our query time still has logarithmic dependency in terms of $n$ and linear dependency in terms of $k$.\n\nAbout the comparison with [7], we would like to mention a few differences between our work and [7]:\n- First, their algorithm is only applicable to the Euclidean metric space, however, our algorithm can deal with a more general case of metric spaces with bounded doubling dimension. \n- Second, the algorithm in [7] is randomized and only works against oblivious adversaries while our algorithm is deterministic and works against adaptive adversaries as well as oblivious ones. \n- Third, the update time of [7] is $O((k/\\epsilon^\\text{ddim}+z)\\log^4{(\\frac{k\\Delta}{\\epsilon\\delta})})$ (as stated in Table 2) which is significantly worse than the update time or the query time of our algorithm. \n\n\n**Question:** The algorithm seems to build on a few existing techniques and the main technical contributions of this paper are not very clear to me. Can you summarize your main technical contributions?\n\n**Response:** We devise a novel approach to make the greedy algorithm for $k$-center with $z$ outliers **dynamic** while the previous dynamic algorithms extract a coreset and run the greedy algorithm on this coreset. We next explain this difference in detail.\n- **Previous dynamic algorithms:** Known dynamic algorithms [3,7,16] for the $k$-center problem with $z$ outliers maintain a coreset after every update. In particular, in [16], they extract the coreset by simply reading the solution from the cover tree. To extract an approximate solution for this problem, one needs to run a known (offline) greedy algorithm on this coreset. In this way, the query complexities of those algorithms are dominated by the running time of the greedy algorithm. \n- **Our dynamic algorithm:** The novelty of our dynamic algorithm is that we make the greedy algorithm itself dynamic. To this end, we use heap data structures to compute a ball that covers the maximum number of points, and dynamic neighborhood sets to obtain points in the expanded maximum ball and update their corresponding keys in the heap to recursively find the next maximum balls.\n"}, {"review_id": "ds9jqjGyhw", "reviewer": "Reviewer_JTLo", "summary": "This paper presents a new algorithm for fully dynamic $k$-center clustering with outliers in spaces with bounded doubling dimension $dim$ and aspect ratio $\\Delta$, where the number of outliers $z$, can be specified at query time. While the approximation ratio of $3+\\epsilon$ is on par with previous results, it trades a $\\log(n)$ dependencies for a removal of a $k$ factor from update and query time and moving $z$ from the problem parameterization to the query specification. In particular, the update time is $1/\\epsilon^{O(dim)} \\log n \\log \\Delta$, and the query time is $k/\\epsilon^{O(dim)} \\log n \\log \\log \\Delta$. Previous algorithms differ in the query time by at least a factor of $(k+z^2) / log(n)$.\n\nThe algorithm builds on the previous result by Pellizzoni et al. and improves its internal tree-based data structure by augmenting additional information. The tree imposes a hierarchy on the input points and stores, for each representative point of a node, a small and a large neighborhood and a list of child points ordered by the number of their descendants. By maintaining the hierarchy for $\\log \\Delta$ choices of the neighbhorhoods' radius (and the fact that the radius of the neighbhorhood scales linearly with the $k$-center cost), the ordered lists allow to construct a $k$-center solution in-place at node level.\n\nOverall, I think this paper showcases nicely how one self-contained improvement to an existing algorithm can lead to an interesting property like time complexity independet of $z$ and actually moving the specification of $z$ from problem paramters to query arguments. The resulting bounds are nice and are an improvement in the interesting case that $k \\in \\Omega(\\log n)$ or $z$ is a variable.", "questions": "-", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Update and/or query time improvement over previous results for $k \\in \\Omega(\\log n)$.\n* The algorithm solves the dynamic $k$-center problem with $z$ outliers for all $z$ simulteanously.\n* The time complexities are independent of $z$.", "weaknesses": "* The time complexities are not better for all settings, and the update time on its own is always slightly worse compared to one other existing algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your time in reviewing our paper and your feedback."}, {"review_id": "WTltIMb7or", "reviewer": "Reviewer_RPz3", "summary": "The main contribution of this paper is the proposal of a new approximate algorithm for \"fully dynamic k center with outliers\" problem in metric space with low doubling dimension. The approximation ratio is 3+$\\epsilon$. The meaning of \"fully dynamic\" is that the algorithm should be able to efficiently adjust its output to accommodate new data when deletion or insertion operations are performed on the dataset. To achieve this goal, we need to maintain a data structure to handle the addition and deletion of data, and to efficiently provide an approximate solution for the k center with outliers problem at any time. According to this paper,  the time complexity of query (given the data structure has been established, to generate a solution for the k center with outliers problem) is $\\epsilon ^{-O(\\mathtt{dim})}k \\log n \\log \\log \\Delta$, where $\\Delta$ is the ratio between the maximum and minimum distance between two points in  dataset, $\\mathtt{dim}$ is the doubling dimension of the metric space. And the time complexity of insertion/deletion  is $\\epsilon ^{-O(\\mathtt{dim})}\\log n \\log \\Delta$.", "questions": "1. Line 148, \"We utilize $\\beta$ to define $R:=\\{0\\}\\cup \\{\\beta \\cdot 2^l | 0 \\le l \\le \\lceil \\log _2 \\Delta \\rceil \\}$ as the set of levels.\".  Does '$l$' have any restrictions here? I guess '$l$' should only take integers? Otherwise, if '$l$' is a real number in this range, the time complexity of Algorithm 1 will be linearly related to $\\log \\Delta$.\n\n2. You mentioned in the paper that the time complexity of Algorithm 1 is linear with respect to $\\log \\log \\Delta$, which is an interesting conclusion because traditional binary search results in time complexity linearly related to log Delta. I noticed that you used some techniques to make this conclusion hold. I wonder if these techniques can be applied to similar binary search scenarios? For example, in [3], the k-center with outliers algorithm based on binary search, can we also obtain a time complexity linearly related to $\\log \\log \\Delta$?", "limitations": "The work is mostly theoretical, and SODA/ICALP/ESA may be better venue for this paper?", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Faster binary search for a specific problem. The \"Query\" algorithm in the paper essentially uses binary search to find the appropriate clustering radius, for example, by searching within the interval $[0, \\Delta]$. This step usually takes $O(\\log \\Delta)$ time, but the technique used in this paper can reduce this complexity to $O(\\log \\log \\Delta)$. This technique appears to be applicable for solving some problems other than the k center with outliers problem.\n2. Lower time complexity in some cases.  The time complexity of addition/deletion operation is independent of the number of cluster centers k and the number of outliers z in the data. And the time complexity of querying is linearly related to the k. This fact gives the algorithm proposed in this paper a significant advantage in terms of running time when k or z is very large.\n\n3. State-of-the-art approximation ratio. The approximation ratio of this algorithm achieves the current state-of-the-art results ($3+\\epsilon$).", "weaknesses": "1. Time complexity. Table 2 in this paper presents a comparison of the time complexity of the proposed algorithm with some existing algorithms for solving the dynamic k center with outliers problem. The table reveals that the previous works (such as [3, 16, 7] in the references) have update and query time complexities that are independent of n, whereas the proposed algorithm has a linear dependence on log n for both update and query. As a result, the proposed algorithm may have slower running times when n is large and k and z are relatively small. \n2. Complex data structures. The algorithm in the text uses relatively complex data structures, which may not be conducive to the implementation of the algorithm and the final actual running time. I am wondering about the space complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:** Time complexity. Table 2 in this paper presents a comparison of the time complexity of the proposed algorithm with some existing algorithms for solving the dynamic $k$ center with outliers problem. The table reveals that the previous works (such as [3, 16, 7] in the references) have update and query time complexities that are independent of $n$, whereas the proposed algorithm has a linear dependence on $\\log{n}$ for both update and query. As a result, the proposed algorithm may have slower running times when $n$ is large and $k$ and $z$ are relatively small. \n\n**Response:** Thank you for pointing this out. Please note that for $n$ distinct points, the spread ratio satisfies $\\Delta \\geq n^{1/\\text{dim}}$ and all mentioned algorithms involve a dependency on $\\log{\\Delta} \\geq \\log{n} / \\text{dim}$. For constant $\\dim$, our query time can be bounded by $ O(\\epsilon^{-\\text{dim}} k \\log{\\Delta} \\log\\log{\\Delta})$, which favorably compares to [16] for example in the regime of $z = O(\\epsilon n)$ where our query time still has a logarithmic dependency on $n$ while [16] would have a quadratic dependency on $n$. Similarly, if either $k$ or $z$ is mildly dependent on $n$, our query time is significantly better than the query time in [16]. Indeed, already for $k \\in O(\\log{n})$ and $z\\in \\Omega(\\sqrt{n})$, the query complexity of [16] would be linear in $n$ compared to the poly-logarithmic dependency in terms of $n$ for our query time.\n\nIn addition, please note that [7] is only for the Euclidean case and is randomized while our algorithm works for doubling metrics and is deterministic, which implies that it can be used for adaptive adversaries rather than only for oblivious adversaries. Also, the update time of [7] is $O((k/\\epsilon^\\text{ddim}+z)\\log^4{(\\frac{k\\Delta}{\\epsilon\\delta})})$ which is significantly worse than the update time or the query time of our algorithm. Moreover, [3] provides a $14$-approximation instead of a $3$-approximation. As mentioned, both algorithms also include a term that depends on n.\n\n\n**Question:** Line 148, \"We utilize $\\beta$ to define $R := \\\\{0\\\\} \\cup \\\\{\\beta\\cdot 2^\\ell | 0 \\leq \\ell \\leq \\log\\Delta \\\\}$ as the set of levels.\". Does '$\\ell$' have any restrictions here? I guess '$\\ell$' should only take integers? Otherwise, if '$\\ell$' is a real number in this range, the time complexity of Algorithm 1 will be linearly related  to $\\log \\Delta$.\n\n**Response:** Yes, you are right, $\\ell$ can take only integers.  Thank you for bringing this to our attention. We will clarify it in the revised version.\n\n\n\n\n\n**Question:** You mentioned in the paper that the time complexity of Algorithm 1 is linear with respect to $\\log{\\log{\\Delta}}$, which is an interesting conclusion because traditional binary search results in time complexity linearly related to log Delta. I noticed that you used some techniques to make this conclusion hold. I wonder if these techniques can be applied to similar binary search scenarios? For example, in [3], the k-center with outliers algorithm based on binary search, can we also obtain a time complexity linearly related to $\\log{\\log{\\Delta}}$?\n\n**Response:** This is because the set that we are searching over only has size $\\log \\Delta$. That is because the radii that we are checking are approximate, so there are only $O(\\log \\Delta)$ candidates of the form $(1+\\epsilon)^i$ to be checked to cover the interval $[1,\\Delta]$. For classical $k$-center, when we are considering a set of $\\Theta(n^2)$ distance candidates (all pairwise distances), then doing binary search over the sorted list of candidates only leads to a $\\log n$ and that cannot be improved to $\\log \\log n$ because it is a different candidate set. We had a look into [3] after your comment and indeed believe that for the query time of their algorithm, $\\log \\Delta$ can be improved to $\\log \\log \\Delta$ in the same fashion.\n"}, {"review_id": "4eFDSpFl0z", "reviewer": "Reviewer_o6fX", "summary": "This paper studies dynamic algorithms for k-center with outliers in a general metric space with bounded doubling dimension, denoted as dim. In the k-center with z outliers problem (which they call (k, z)-center problem), the goal is to find a set of k points C, such that the maximum distance from the data points to the center set is minimized, where the maximization is taken only over the n - z closest data points to C. In terms of the dynamic model, the paper assumes oracle access to the distance function, subject to point insertion and deletions. The query is to return a list of approximate centers, which is of size (at most) k.\n\nThe main result is a dynamic algorithm that can handle each update in time eps^{-dim} log n, which is independent of k, and can report a (3 + eps)-approx solution in eps^{-dim} k log n time. The running time is completely independent of z, and for the query in linear in k which improves the (k + z)^2 query time from previous works significantly.\n\nThe techniques are based on previous navigating net/cover tree structures. However, nontrivial steps are employed to obtain the improved bounds.", "questions": "- Table 1, line 2, eps^d -> eps^{-d}. Also line 1 is using 1 / eps, which is inconsistent with eps^{-d} style.\n-  Page 2, line 57: I agree that wlog you can assume d_\\min = 2 if it is the static setting, where P is given. However, in the dynamic setting, the aspect ratio and/or d_min could change very significantly. Do you assume the d_min is always = 2, and that the aspect ratio is always bounded, at any time step?\n- Did you define doubling dimension at all? Also, in line 175, you mentioned it has 2^{O(dim)} children. This is probably standard, but it still requires some explanation, or at least requires a reference.\n- In sec 2 you defined a data structure. It would be helpful to state what updates/queries it supports and what's the guarantee in e.g. a lemma statement.\n- The \"Overview\" of Sec 3 seems too detailed and without a big picture. For example, it starts with a discussion of what we do for the heaps, but did not explain what's the overall purpose of this MaxCoeverage procedure.", "limitations": "I don't find a clear discussion these. But I suppose there is no potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The result is strong. In particular, the running times are independent of z, and the query time is only linear in k which improves over (k + z)^2 as in previous works. I find this improvement significant.\n- The comprehensive comparison to various recent works helps a lot in gauging the novelty of this work.\n- Technically, although the approach is not novel in terms of overall framework, to fit ideas from several different works together is a nontrivial task, and I find it interesting.", "weaknesses": "- The setting of doubling metrics is only partially motivated. Indeed, Bateni et al. [1] showed \\Omega(k) is necessary for handling updates in general metrics, but what about the dependence in z? It seems removing the dependence in z in general metrics is still an important goal of study?\n- There is no empirical evaluation of your algorithm, which may be important for some in the NeurIPS community.\n- I don't find a statement of the main theorem. A rigorous statement may be helpful for people who would like to cite/use your paper without going too much into detail. Also, this makes it somewhat difficult to read your proofs, since it's easy to get lost in the series of lemmas and I don't see the big picture.\n- The presentation is not very friendly for non-experts. People without sufficient background in doubling metrics and k-center clustering may find it difficult to understand the paper. I personally only manage to check part of the proofs, although I think it overall makes sense.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:** I don't find a statement of the main theorem. A rigorous statement may be helpful for people who would like to cite/use your paper without going too much into detail. Also, this makes it somewhat difficult to read your proofs, since it's easy to get lost in the series of lemmas and I don't see the big picture.\n\n**Response:** The main theorem is formally stated on pages 2-3 (Theorem 1.1). The proof of this theorem can be found in the appendix (page 18 of the full version).\n\n\n**Question**: Page 2, line 57: I agree that wlog you can assume $d_{\\min} = 2$ if it is the static setting, where P is given. However, in the dynamic setting, the aspect ratio and/or $d_{\\min}$ could change very significantly. Do you assume the $d_{\\min}$ is always = 2, and that the aspect ratio is always bounded, at any time step? \n\n**Response:** To have a dynamic aspect ratio, we can assume that the navigating net has an infinite number of levels (by defining $R:=\\set{0} \\cup \\set{\\beta \\cdot 2^{\\ell}| \\ell \\in \\mathbb{Z}}$), however, only $O(\\log{\\Delta})$ levels are active at a time. We consider the highest level with $n$ nodes for $d_{\\min}$ and the lowest level with only one node for $d_{\\max}$. Thank you for bringing this to our attention. We will clarify it in the revised version.\n\n**Question**: Did you define doubling dimension at all? Also, in line 175, you mentioned it has $2^{O(\\text{dim})}$ children. This is probably standard, but it still requires some explanation, or at least requires a reference.\n\n**Response:** Doubling dimension is defined in Line 54. We will highlight it with more details in the revised version.\n\n**Question**: In sec 2 you defined a data structure. It would be helpful to state what updates/queries it supports and what's the guarantee in e.g. a lemma statement.\n\n**Response:** The update time of our data structure is specified in Lemma 2.3. We will explain the update/query methods that our data structure supports in greater detail in the revised version.\n\n**Question**: The \"Overview\" of Sec 3 seems too detailed and without a big picture. For example, it starts with a discussion of what we do for the heaps, but did not explain what's the overall purpose of this Max Coverage procedure.\n\n**Response:** Thank you for bringing this to our attention. We will provide a big picture of our algorithm in the revised version. \n"}]

Author rebuttal:
We would like to thank the reviewers. We appreciate your time in reviewing our paper and your feedback. Here are our responses to the questions. We will address any minor errors like typos and proposed references promptly.

Meta-review: All reviewers support the paper due to the importance of the problem as well as the significant improvement in the runtime compared with previous works, which is now nearly optimal in certain parameters.
Decision: Accept (poster)