Research map / Learning theory and algorithms / Clustering
Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces
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 (4+ε)-approximation for (k,z)-center with outliers in general metric spaces, allowing (1+ε)z outliers, with amortized update time O(ε^-3 k^6 log k log Δ), improving on the prior (14+ε) result.
Problem
Maintaining an approximate k-center clustering with z outliers under point insertions and deletions in general metric spaces, with update time independent of z and n.
Approach
Combines the sampling-based level data structure of Chan et al. with the greedy charging strategy of Charikar et al.; maintains at most k levels with a dense invariant, reclustering only a level and above when its cluster becomes too sparse, and uses an artificial-outlier charging argument to get a 4+ε factor.
Key results
- Maintains a (4+ε)-approximate (k,z)-center solution allowing (1+ε)z outliers with high probability, improving on the prior (14+ε) dynamic algorithm of Chan et al.
- Expected amortized update time O(ε^-3 k^6 log(k) log(∆)), independent of z and of the current number of points.
- Theoretical result only; no experiments reported.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed fully dynamic algorithm instead of Chan et al. [5] | (k, z)-center clustering in general metric spaces · (k, z)-center clustering, general metric spaces | approximation factor: (14 + ϵ) -> (4 + ϵ) | Helped |
| Use the proposed update strategy instead of Chan et al. [5] | (k, z)-center clustering in general metric spaces · (k, z)-center clustering, general metric spaces | update-time dependence on z and current point count | Helped |
| Require centers to be currently active points | Proposed fully dynamic algorithm · (k, z)-center clustering, discrete version | approximation factor: (4 + ϵ) -> 6 | Hurt |
Limitations
- Allows (1+ε)z outliers rather than exactly z.
- Non-discrete centers; a 6-approximation is needed when centers must be active points.
- Update time has a large polynomial dependence on k (k^6).
Experimental setup
Metrics: approximation ratio amortized update time
Baselines: Chan et al. (14+ε)-approximation dynamic algorithm
Builds on: Chan et al. fully dynamic (k,z)-center algorithm Charikar et al. greedy 3-approximation for k-center with outliers Bateni et al. fully dynamic k-center
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)
- Dynamic k-center clustering with lifetimes (NeurIPS 2026 · similarity 0.90)
- Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.89)
- Fully-Scalable Massively Parallel Algorithm for k-center with Outliers (AAAI 2025 · similarity 0.88)
- Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond (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.