Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse

We thank all the reviewers for their efforts and insightful comments. Please let us know if you have any questions about our rebuttal.

Thank you for pointing this out; this will help us improve the clarity of the proofs. Indeed, since $\beta = O(\log (n/k))$, there is a $\log (n/k)$ factor hidden in $\Tilde{O}(k) = O(k \cdot \log (n/k))$, which also adhere our use of notation $\Tilde{O}$ (please see footnote $2$ in page $2$). We will point this out clearly in the Notation section instead of the footnote. Note that this will not break down the proof of Theorem 1.3 since no matter what is the size of the space (either $n$ before using sparsifier, or $\beta \cdot k = k \log (n/k)$ after using sparsifier) the recourse would be constant since we are calling the algorithm of Theorem 1.2 on this space which has constant recourse (i.e. $R_A(\cdot) = O(1)$ in Line 312).

You are right about the comment on page 8. There is a typo in Line 435, we should have written: ``each $S_j$ has size $O(k)$". The rest of the analysis remains intact and correct. Due to space constraints, we could not elaborate more on the proofs in the paper. Below, we explain the proof in more detail (note that the current proof in the paper is self-contained and this explanation does not add any new ideas or change the proof):

Clarification on the proof: Note that the recourse is defined as the number of changes in the output of the sparsifier $U = S_1 \cup S_2 \cup \cdots \cup S_{\ell-1} \cup U_\ell$ (see line 13 of Algorithm 1), and by reconstructing from $U_i$, the sets undergoing changes in the output are $S_i, S_{i+1}, \ldots, S_{\ell-1}$ and $U_\ell$. This concludes the total change in the output $U$ is at most $O(k(\ell-i+1))$ since each $S_j$ has size $O(k)$, as well as $U_\ell$. Although $|U_1| = O(n)$, the sizes of $U_i$s decrease exponentially according to Lemma 3.11, which is the key fact that we use to bound the recourse.

The recourse caused by reconstructing from $U_i$ is at most $O(k(\ell-i+1))$ as explained above. Since the sizes of $U_i$s decrease exponentially (according to Lemma 3.11) until it becomes $|U_\ell| = \Theta(k)$, we get $\ell - i = O(\log(|U_i|/k))$. Since we only start the reconstruction from $U_i$ every $\Omega(|U_i|)$ steps, the amortized recourse incurred by all the reconstructions starting from level $i$ would be bounded by $\frac{k}{|U_i|} \cdot \log \left( \frac{|U_i|}{k} \right)$. The rest of the analysis follows from the bound on the potential function defined in the paper.

We thank all the reviewers for their efforts and insightful comments. Please let us know if you have any questions about our rebuttal.

It is known that an update time of $\Omega(k)$ is necessary for this problem. As stated in Line 58 in the introduction, it is known that, in the static setting, a running time of $\Omega(nk)$ is necessary to achieve any non-trivial approximation (Bateni et al. 2023). Any dynamic algorithm with $o(k)$ update time yields a static algorithm with $o(nk)$ running time, which rules out any non-trivial approximation ratio. Hence, $\Omega(k)$ update time is necessary in the dynamic setting, which means that $\tilde{O}(k)$ update time is near optimal (up to polylog factors).

Indeed, when we say that our algorithm succeeds with high probability at every update, we mean that the approximation ratio holds with high probability after handling each update (please see Footnote 5 in Theorem 1.3).

We thank all the reviewers for their efforts and insightful comments. Please let us know if you have any questions about our rebuttal.

Our algorithm can be implemented to have an update time of $O(k \cdot \log^4 n \log \Delta)$ by using standard data structures. Regarding the approximation ratio and recourse, we did not optimize our analysis of the constants in these bounds for the sake of simplicity. By carrying out a more intricate analysis of the sparsifier, we can show that our approximation ratio is at most $20$---this is the best approximation ratio of any algorithm with constant recourse, even if we allow exponential update time. In particular, the previous smallest was $24$ by Lacki et al. [SODA'24]. Furthermore, by slightly tweaking how we use the sparsifier, we can get a recourse of at most $4 + \epsilon$, for any constant $\epsilon > 0$ (we note that the best we can hope to achieve here is a recourse of $2$, since in the worst case we must remove a point and insert a new point). We tried to keep the proofs simple and provide asymptotic bounds. Although the constants in the approximation ratio and recourse are not specified in the current analysis, they are good in practice.

We implemented our algorithm and compared the approximation ratio of our algorithm with the static $2$-approximation offline greedy algorithm by Gonzalez; we observed that the quality of the solution maintained by our algorithm is significantly better than what is derived by the current analysis. Specifically, we tested our dynamic algorithm on 5 different datasets, on inputs of size $n = 10000$ with $k = 10, 50$ and $100$, and compared the cost of the solution maintained by our algorithm to the cost of the solution produced by the offline greedy algorithm. We observed that the cost of the solution produced by our algorithm is consistently within a factor of 1.25 - 1.75 of the cost of the greedy algorithm.

Regarding recourse, we also observed that the amortized recourse of our algorithm is actually sublinear in practice, at most $1$ in almost all of our test results.

We will improve the accuracy of the statements in the paper and provide precise guarantees. We will also improve the analysis and provide a clear road map together with a natural flow for the analysis to be easy to follow for the reader.

Thank you for pointing out the results that we missed mentioning in our paper. We will add them to the introduction and the related work sections of our paper.

Regarding the query time, note that our algorithm maintains the solution explicitly after every update. Without considering an explicit solution after every update, we can not define the notion of recourse. In this framework, the query time is subsumed by the update time since we can assume there is a query after every update as the solution must be maintained explicitly. We will mention this clearly in the introduction to prevent any confusion.

We thank all the reviewers for their efforts and insightful comments. Please let us know if you have any questions about our rebuttal.

In order to keep the proofs simple, we did not optimize the constant in the approximation ratio in the paper. By carrying out a more intricate analysis of the sparsifier, we can show that our approximation ratio is at most $20$---this is the best approximation ratio of any algorithm with constant recourse, even if we allow exponential update time. In particular, the previous smallest was $24$ by Lacki et al. [SODA'24]. We have also done some experiments and compared the approximation ratio of our algorithm with the static $2$-approximation offline greedy algorithm by Gonzalez; we observed that the quality of the solution maintained by our algorithm is significantly better than what is derived by the current analysis. Specifically, we tested our dynamic algorithm on 5 different datasets, on inputs of size $n = 10000$ with $k = 10, 50$ and $100$, and compared the cost of the solution maintained by our algorithm to the cost of the solution produced by the offline greedy algorithm. We observed that the cost of the solution produced by our algorithm is consistently within a factor of 1.25 - 1.75 of the cost of the greedy algorithm.

Thank you for pointing out the issue with using the DynamicMIS algorithm as a black box. We will elaborate on this and clarify this point.