Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
Authors: Sayan Bhattacharya, Martin Costa, Ermiya Farokhnejad, Silvio Lattanzi, Nikos Parotsidis
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our contribution: We give an algorithm for dynamic kcenter that answers this question in the affirmative, obtaining the following result. Theorem 1.1 (informal). There is an algorithm for dynamic k-center that maintains a 20-approximation with O(k log5(n) log ) update time and O(1) recourse. We obtain our result by combining a simple variant of the algorithm of (Bateni et al., 2023) with the dynamic sparsification algorithm of (Bhattacharya et al., 2023a). |
| Researcher Affiliation | Collaboration | 1Department of Computer Science, University of Warwick 2Google Research. Correspondence to: Sayan Bhattacharya <EMAIL>, Mart ın Costa <EMAIL>, Ermiya Farokhnejad <EMAIL>, Silvio Lattanzi <EMAIL>, Nikos Parotsidis <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Reconstruct 1: for i = 1 to ℓdo 2: COUNT[i] = COUNT[i] + 1 3: end for 4: j = smallest index s.t. COUNT[j] |Uj|/4 5: for i = j to ℓdo 6: COUNT[i] = 0 7: end for 8: repeat 9: for m = 1 to M = Θ(log n) do 10: (Am, Bm) Almost Cover(Uj) 11: end for 12: m arg min1 m M cl(Am, Uj \ Bm) 13: (Sj, Uj+1) (Am , Bm ) 14: j = j + 1 15: until |Uj| 16k 16: ℓ= j 17: U := S1 Sℓ 1 Uℓ |
| Open Source Code | No | The text is ambiguous or lacks a clear, affirmative statement of release. |
| Open Datasets | No | The paper focuses on theoretical algorithm design within an abstract 'metric space (V, d)' and does not describe or use any specific datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on specific datasets, therefore, no dataset splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and analysis, not empirical experiments. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper discusses theoretical algorithms and components like 'Dynamic MIS' and 'Almost Cover' but does not specify any programming languages, software libraries, or their version numbers used for implementation. |
| Experiment Setup | No | The paper is theoretical and does not present empirical experiments. Consequently, there are no details on experimental setup, hyperparameters, or training configurations. |