Research map / Learning theory and algorithms / Clustering
Fully Dynamic $k$-Clustering in $\tilde O(k)$ Update Time
Sayan Bhattacharya, Martin Costa, Silvio Lattanzi, Nikos Parotsidis
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace dynamic coreset maintenance with the lazy, layered MP-based dynamic algorithm | OurAlg-500 versus HK-1000 · Five UCI datasets, k=10, 50, 100 | total update time: HK/OurAlg ratios: 31.774–377.350 | Improved |
| Replace dynamic coreset maintenance with the lazy, layered MP-based dynamic algorithm | OurAlg-500 versus HK-1000 · Five UCI datasets, k=10, 50, 100 | solution cost: HK/OurAlg ratios: 0.988–1.538 | Mixed |
| Replace dynamic coreset maintenance with the lazy, layered MP-based dynamic algorithm | OurAlg-500 versus HK-1000 · Five UCI datasets, k=10, 50, 100 | query time: HK/OurAlg ratios: 0.558–2.629 | Mixed |
| Increase OurAlg sampling parameter from 250 to 1000 (ablation) | OurAlg · Evaluated datasets | average query time: roughly 3 times slower | Hurt |
| Increase HK sampling parameter from 250 to 1000 (ablation) | HK · Evaluated datasets | average query time: 11 times slower | Hurt |
| Vary OurAlg sampling parameter across tested settings (ablation) | OurAlg · Evaluated datasets | solution quality: less than 1% | No clear effect |
| Vary HK sampling parameter across tested settings (ablation) | HK · Evaluated datasets | solution quality: 3-9% | Mixed |
Closest papers by meaning
- Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse (ICML 2025 · similarity 0.93)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.90)
- Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.90)
- Dynamic k-center clustering with lifetimes (NeurIPS 2026 · similarity 0.89)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.88)
- Dynamic Algorithm for Explainable $k$-medians Clustering under $\ell_p$ Norm (NeurIPS 2025 · 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.
