Research map / Learning theory and algorithms / Clustering
Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a fully dynamic metric k-center algorithm with 20-approximation, O(1) amortized recourse and near-linear-in-k update time by composing a dynamic MIS-based threshold-graph algorithm with a Mettu-Plaxton-style dynamic sparsifier.
Problem
Fully dynamic metric k-center under point insertions and deletions, jointly optimizing approximation ratio, recourse, and update time.
Approach
Combines a simplified variant of Bateni et al.'s threshold-graph/MIS k-center algorithm, made stable with nested MISs, with a dynamic sparsifier (Bhattacharya et al.) that reduces the metric to size O(k log(n/k)), yielding O(1) recourse and near-optimal update time simultaneously.
Key results
- Maintains a 20-approximation for dynamic metric k-center with O(k log^5(n) log Delta) amortized update time and O(1) amortized recourse (theoretical).
- Dynamic MIS-based base algorithm achieves 8-approximation with 4 expected recourse against oblivious adversaries.
- A modified sparsifier reduces the total recourse to 8+epsilon, and to 4+epsilon if centers may be opened outside the current space.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Nest the MISs across threshold graphs | Dynk · Dynamic metric k-center | recourse: 4 | Helped |
| Nest the MISs across threshold graphs | Dynk · Dynamic metric k-center | approximation ratio: 8 | Mixed |
| Compose Dynk with the standard dynamic sparsifier | Nested-MIS algorithm (Dynk) · Dynamic metric k-center | approximation ratio: 8 -> 20 | Hurt |
| Compose Dynk with the standard dynamic sparsifier | Nested-MIS algorithm (Dynk) · Dynamic metric k-center | update time: O(n \log^4 (n) \log \Delta) -> O(k \log^5 (n) \log \Delta) | Helped |
| Compose Dynk with the standard dynamic sparsifier | Nested-MIS algorithm (Dynk) · Dynamic metric k-center | recourse: 4 -> O(1) | No clear effect |
| Use BSparsifier with q = 4/\epsilon instead of the standard sparsifier (ablation) | Proposed algorithm · Dynamic metric k-center | recourse: O(1) -> 8 + \epsilon | Helped |
| Keep deleted centers while their clusters remain non-empty (ablation) | Proposed algorithm with BSparsifier · Dynamic metric k-center with centers outside the input space | recourse: 8+\epsilon -> 4+\epsilon | Helped |
Limitations
- Guarantees hold against oblivious adversaries only; approximation holds with high probability.
- Recourse of the base algorithm is 4 or 8 plus epsilon, not optimal constant 2.
- Update time includes log factors and log Delta dependence.
Experimental setup
Metrics: approximation ratio amortized recourse amortized update time
Baselines: Bateni et al. (SODA'23) Lacki et al. Bhattacharya et al. (NeurIPS'23)
Builds on: Bateni et al. dynamic k-center Bhattacharya et al. dynamic sparsifier Mettu-Plaxton algorithm Behnezhad et al. dynamic MIS
Closest papers by meaning
- Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.93)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.91)
- Dynamic k-center clustering with lifetimes (NeurIPS 2026 · similarity 0.91)
- Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond (NeurIPS 2025 · similarity 0.88)
- Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.88)
- Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.