Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces

Comment: Time complexity. The amortized update time $\epsilon^{-2}k^6\log k\log \Delta$ is worse than the method in [5] (if $k$ is large), whose time complexity is $O(\frac{k^2\log\Delta}{\epsilon^2\tau}\log^2\frac{1}{\delta})$.

Comment: High update time complexity in the worst case. The proposed algorithm still need $O(n\epsilon^{-1}k^3\log k\log\Delta)$ time to handle an insertion or deletion of a single point in the worst case.

Response: Besides the improvement in approximation factor with respect to the algorithm in [5], another interesting aspect of our method is that it is adversarially robust, meaning it can handle an adversary who observes the computed solution after each update and adjusts the subsequent updates accordingly. In contrast, the dynamic $14$-approximation algorithm developed by Chan et al. is not adversarially robust. In particular, if their solution is revealed at any time, the adversary can impose an expensive update that requires time in $\Omega(n)$.

Regarding the question about handling an insertion or deletion of a single point in the worst case with $O(n \epsilon^{-1} k^3 \log k \log \Delta)$ time, we believe this can be managed with some adjustments to our algorithm. Specifically, we propose running two parallel instances of our algorithm. In the first instance, we compute and output the solution, while the second instance divides the large operations of $O(n \epsilon^{-1} k^3 \log k \log \Delta)$ time into smaller chunks of size $\text{poly}(\epsilon^{-1}, k, \log k, \log \Delta)$ and processes each chunk sequentially after an update. When the solution maintained by the first run becomes invalid—potentially after $\Omega(n)$ updates—we switch to the second run, obtain the solution from there, and continue the process. It is important to note that when switching between runs, we obtain a new solution and maintain that updated solution.

Comment: No experimental result. [...] I strongly encourage the authors to compare the performance of both running time and cost to [5].

Response: We agree with the reviewer that providing empirical results or practical evaluations would be valuable and interesting work. Our main focus was to improve the $14$-approximation guarantee and determine how much we could refine the approximation factor, leading to the development of the first adversarially robust dynamic $4$-approximation algorithm for the metric $k$-center problem with outliers. We consider conducting experiments and benchmarking our dynamic algorithm against the algorithm by Chan et al. for both real and synthetic scenarios as future work.

Question: About the time complexity of binary search of $r_{OPT}$, you have mentioned that the set of all possible $r$ is $R=\{(1+\epsilon)^i\colon d_{\min} \leq (1+\epsilon)^i \leq d_{\max}, i\in N\}$. So $|R| = \log_{1+\epsilon}\Delta = \frac{\log\Delta}{\log(1+\epsilon)}$. So if you binary search the set $R$, it seems like you only need $O(\log|R|) = O(\log\log\Delta)$ steps. So can your time complexity improved to $O(\epsilon^{-2}k^6\log k\log\log\Delta)$?

Response: For each guess $r \in R$, we run an instance of the algorithm for that specific $r$. After each insertion or deletion, we update all these instances. As a result, the update time is affected by a factor of $|R| = \log_{1+\epsilon} \Delta = O(\epsilon^{-1}\log{\Delta})$. We apologize for any confusion caused by the title of that paragraph and will revise it accordingly.

Question: If I want to delete some point which is also a center of the solution. I think this center point should also be deleted since this point has been removed from this metric space. But it seems that Procedure 2 in the paper do not consider this situation. How do your algorithm handle the deletion of the center points?

Response: As mentioned in the paper, we studied the non-discrete version of the problem, where centers can be any point in the metric space. Therefore, a center can be a deleted point. We would like to thank you for bringing to our attention the interesting question about the discrete version of the problem we study in the paper. Indeed, we have thought about this question during the short rebuttal period and have provide a proof that explains how our dynamic data structure can also provide a $6$-approximation solution for the discrete metric $k$-center problem with outliers, where centers must be selected from the input set of points. You can find the proof of this claim in the response to reviewer CFX4. We also attached a figure in the global rebuttal for a visual representation. Note that any feasible solution for the discrete version is also feasible for the non-discrete version. Therefore, the optimal radius for the discrete version is at least as large as that for the non-discrete version. This implies that, for some applications, the non-discrete version can offer more precise clustering. We believe both the discrete and non-discrete versions are important, each being better suited for different applications. Besides the improvement in approximation factor, another interesting aspect of our method is that it is adversarially robust, meaning it can handle an adversary who observes the computed solution after each update and adjusts the subsequent updates accordingly. In contrast, the dynamic $14$-approximation algorithm developed by Chan et al. is not adversarially robust. In particular, if their solution is revealed at any time, the adversary can impose an expensive update that requires time in $\Omega(n)$.

Question: What is the size of your memory usage?

Response: The space complexity of our algorithm is $O(\epsilon^{-1}\log(\Delta)n)$. This is because we maintain $\epsilon^{-1} \log(\Delta)$ instances corresponding to different radius guesses, each containing up to $n$ points. The space required to temporarily store the sample sets used in Algorithm $`OfflineCluster`$ is in $O(n)$.

Comment: Personally, I wouldn't agree that this is an improvement over the work of Chan et al. [5]. Indeed, it does achieve a better approximation ratio, but at the cost of increasing the runtime. The paper indeed provides a new, interesting trade-off, but I believe the abstract we should discuss this more carefully.

Response: Thank you for the comment. We will discuss this trade-off in more detail in the full version. Besides the improvement in approximation factor, another interesting aspect of our method is that it is adversarially robust, meaning it can handle an adversary who observes the computed solution after each update and adjusts the subsequent updates accordingly. In contrast, the dynamic $14$-approximation algorithm developed by Chan et al. is not adversarially robust. In particular, if their solution is revealed at any time, the adversary can impose an expensive update that requires time in $\Omega(n)$.

Comment: Regarding techniques,[...] I would encourage the authors to discuss differences/similarities between Mett-Plaxton and their work. In my opinion, this doesn't diminish the contribution of the paper at hand.

Response: Thank you for highlighting the work of Mettu and Plaxton on 'Optimal Time Bounds for Approximate Clustering' and the subsequent research. We will be sure to discuss the differences and similarities between the work of Mettu and Plaxton and ours.

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

Response: Thank you for the valuable suggestions. We will make sure to add more references and the mentioned definitions at the correct positions in the full version.
The subset $P_i$ of points not covered in level $i$ is disjoint from the clusters $C_1,\ldots,C_{i-1}$. Hence, a clustering of $P_i$ does not need to contain these clusters. Similarly, a deletion of a point at level $i$ does not lead to a violation of the invariants in levels $1,\ldots,i-1$, but can potentially violate the invariants at higher levels. Therefore, we only need to recluster the levels from $i$ upwards. We will make sure to write this part more clearly in the full version.

Question: Major comment/question: Line 146 -- can you ,[...] Does the work of Chan et al. [5] have the some restriction?

Response: We would like to thank you for bringing to our attention the interesting question about the discrete version of the problem we study in the paper. Indeed, we have thought about this question during the short rebuttal period and determined how our dynamic data structure can also provide a $6$-approximation solution for the discrete metric $k$-center problem with outliers, where centers must be selected from the input set of points. Observe that any feasible solution for the discrete version is also valid for the non-discrete version. Therefore, the optimal radius in the discrete version is at least as large as that in the non-discrete version. This suggests that, in certain applications, the non-discrete version may provide more precise clustering. We believe that both the discrete and non-discrete versions are valuable, each being particularly suited to different applications. Chan et al. [5] consider the discrete version; however, they need to reconstruct the leveling after the deletion of a center, making their algorithm not adversarially robust.

Here, we prove how our data structure can also offer a $6$-approximation solution for the discrete version. We also attached a figure in the global rebuttal for a visual representation.

Claim: Our data structure can report a $6$-approximation solution for the discrete version of the $k$-center problem with $z$ outliers without increasing the time or space complexity.

Proof: Let $r$ and $i$ be fixed, and $c_i$ be the center of cluster $C_i=B(c_i,4r)$ (Recall that $B(x,\rho)$ is the ball of radius $\rho$ centered at $x$). To provide a solution for the discrete version, we do the following.

As long as $c_i$ is not deleted, we report $c_i$ as the $i$-th center. After the deletion of the point $c_i$, we consider two cases: $\min(z+1,\frac{n_i-z}{k-i+1}-\frac{\epsilon z}{\alpha k})\leq 0$ or $\min(z+1,\frac{n_i-z}{k-i+1}-\frac{\epsilon z}{\alpha k})>0$. For the first case we have $n_i<(1+\epsilon)z$ as $i\geq 1$ and $\alpha>1$. Hence, we can report all the $n_i$ points as outliers and stop. The dense invariant states that $|B(c_i,2r\cap P_i|\geq\min(z+1,\frac{n_i-z}{k-i+1}-\frac{\epsilon z}{\alpha k})$. Therefore, $|B(c_i,2r)\cap P_i|>0$ holds in the second case and there exists a point $\hat{p}\in B(c_i,2r)$. Then we report the point $\hat{p}\in B(c_i,2r)$ after the deletion of $c_i$.

We next prove the $6$-approximation guarantee. To do this, we show that $C_i\subseteq B(\hat{p},6r)$. This implies that any feasible solution in our data structure with radius $4r$ for the non-discrete version can be used to report a feasible solution for the discrete version. Also, see attached the figure in the global rebuttal for a visual representation. Let $q\in C_i$. We show that $q\in B(\hat{p},6r)$. Since $q\in C_i=B(c_i,4r)$, we have $d(q,c_i)\leq 4r$ , where $d$ is the distance function. Moreover, $d(c_i \hat{p}) \leq 2r$ since $\hat{p}\in B(c_i,2r)$. Then by the triangle inequality we have $d(q, \hat{p}) \leq d(q,c_i)+d(c_i,\hat{p})\leq 4r+2r=6r.$

The complexity of space and time remains to be discussed. To report a solution for the discrete version, it is enough to keep $B(c_i,2r)\cap P_i$. Note that our data structure already stores $C_i\cap P_i$ , and since $B(c_i,2r)\cap P_i \subseteq C_i\cap P_i$ , the space complexity and time complexity remain the same.

Comment: the update time complexity $O(\varepsilon^{-2}k^6\log{k}\log{\Delta})$ is not competitive, particularly for large $k$.

Response: Our goal was to develop a dynamic algorithm with a low approximation guarantee and a simple, elegant data structure. We did not focus on optimizing the exponent of $k$ in our running time. An interesting aspect of our method is that it is adversarially robust, meaning it can handle an adversary who observes the computed solution after each update and adjusts the subsequent updates accordingly. In contrast, the dynamic $14$-approximation algorithm developed by Chan et al. is not adversarially robust. If their solution is revealed at any time, the adversary can impose an expensive update that requires time in $\Omega(n)$.

Comment: The paper does not provide empirical results or practical evaluations of the algorithm, which could demonstrate its performance in real-world scenarios.

Response: We agree with the reviewer that providing empirical results or practical evaluations would be valuable and interesting work. Our main focus was to improve the $14$-approximation guarantee and determine how much we could refine the approximation factor, leading to the development of the first adversarially robust dynamic $4$-approximation algorithm for the metric $k$-center problem with outliers. We consider conducting experiments and benchmarking our dynamic algorithm against the algorithm by Chan et al. for both real and synthetic scenarios as future work.

Question: Can this method be slightly modified to support the change of $k$ and $z$. Alternatively, is there any negative results on handling the dynamic $k$ and $z$.

Response: Our data structure is designed with up to $k$ levels, based on known values of $k$ and $z$. We are unsure how to modify our data structure to handle changes in $k$ and $z$ during the execution of the algorithm. Investigating the development of such a dynamic algorithm would indeed be an interesting challenge.

Question: Does the analysis of the algorithm include a specific space complexity? Additionally, i am curious about the hardness of the fully-dynamic clustering with outliers. Can you provide the lower bounds of the space and the update time in the context of the fully-dynamic setting?

Response: The space complexity of our algorithm is $O(\epsilon^{-1}\log(\Delta)n)$. This is because we maintain $\epsilon^{-1} \log(\Delta)$ instances corresponding to different radius guesses, each containing up to $n$ points. For the sample sets needed in $`OfflineCluster`$, we also need $O(n)$ space because they form a subset of the dataset. Establishing a space lower bound for fully dynamic algorithms for $k$-center with outliers would be an intriguing question.

Comment: The algorithm is randomized and works only against oblivious adversaries. This is a shared characteristic with the previous paper on this topic.

Question: Is there a good reason why the algorithm is randomized? What are the obstacles to obtaining deterministic algorithms in this model?

Response: We address these two points together in our response. Interestingly, we have discovered that our dynamic algorithm not only can handle oblivious adversaries but is even adversarially robust. A dynamic algorithm is called adversarially robust if its performance guarantees (including the approximation factor and update time) are preserved even when the sequence of updates (i.e., insertions and deletions) is adaptively chosen by an adversary who observes the outputs of our algorithm throughout the sequence and adjusts them accordingly. An adversarially robust dynamic algorithm is more powerful than one designed to handle only an oblivious adversary, as an oblivious adversary cannot access the algorithm's outputs after each update. In particular, we only use random bits to sample from large clusters at each level and maintain a solution. (This is the only component of our algorithm that uses randomness.) The adversary, however, can observe the maintained solution after each update and adaptively modify future updates (insertions and deletions) accordingly. In contrast, the dynamic $14$-approximation algorithm developed by Chan et al. is designed only for oblivious adversaries and is therefore not adversarially robust. In particular, if their solution were revealed at any time, the adversary could impose costly update time $\Omega(n)$.

Question: The factor of $k^6$ in your upper bound is large. Is there a reason why in practice the algorithm would be significantly less costly?

Response: Thank you for raising this interesting question. The worst case occurs when the gap between the size of the ball chosen in the offline algorithm and the threshold is negligible, but we believe this is not always the case in practice. To increase this gap, we propose selecting the ball of maximum size in Line 8 of the OfflineCluster procedure. This adjustment does not change the theoretical bounds but can make the algorithm faster in practice.