New Algorithms for Fully-Dynamic k-center with Outliers

Junyu Huang, Zhize Li, Zhen Zhang, Xujia Li, Jianxin Wang, Qilong FengICML 2026 · OpenReview

Clustering is a cornerstone of unsupervised learning, and the $k$-center problem is one of its most fundamental formulations: find $k$ points (centers) such that the maximum distance from any data point to its nearest center is minimized. However, real-world data is rarely static or pristine. It arrives and disappears in continuous streams (fully-dynamic) and is often noisy, containing "outliers" that can pull cluster centers away from meaningful data.

This paper introduces a novel layered-sampling framework for the fully-dynamic $k$-center with outliers problem. By replacing traditional "radius guessing" with an adaptive hierarchy of sampled points, the authors achieve update and query times that are completely independent of the data's aspect ratio, while maintaining a constant-factor approximation.

The Bottleneck: Radius Guessing and Aspect Ratio

The primary challenge in dynamic clustering with outliers lies in computational efficiency. Existing dynamic algorithms for this problem typically rely on radius guessing. They maintain a range of possible optimal radii and update data structures for each candidate radius.

Consequently, their running time depends heavily on the aspect ratio ($\Delta$)—the ratio between the maximum and minimum pairwise distances in the dataset. If a dataset contains points that are densely packed alongside others that are vastly spread out, $\Delta$ explodes, causing these algorithms to slow down significantly. The authors set out to build an algorithm that is "$\Delta$-independent," ensuring it remains fast regardless of the data's spatial distribution.

A Novel Approach: The Layered-Sampling Framework

To bypass the need for radius guessing, the authors propose a Layered-Sampling framework. Instead of guessing a radius upfront, the algorithm builds a hierarchy of three distinct layer types to adaptively "peel" the data:

  1. Greedy-Coverage (Type-1): These layers use small random samples to cover the majority of "inliers" (the legitimate points we want to cluster). The uncovered set of points shrinks geometrically at each step.
  2. Transition Layer (Type-2): Once the uncovered set is small enough to be comparable to the outlier budget ($z$), a larger sample is taken. This ensures that even smaller, legitimate clusters are adequately represented.
  3. Fine-Grained Division (Type-3): These final layers slowly incorporate the remaining points in small batches, ensuring the algorithm doesn't accidentally discard too many valid points as outliers.

To maintain efficiency in a fully-dynamic setting (handling both insertions and deletions), the authors implement an update-delay rule. Rather than rebuilding the entire structure for every single change, the algorithm uses counters. A layer is only reconstructed when the number of changes exceeds a specific fraction of that layer's size. This amortizes the computational cost over many operations, leading to highly efficient update times.

Key Innovations

  • Breaking the $\Delta$ Dependency: By using the distances to sampled representatives to define the covering radius adaptively, the algorithm entirely bypasses the need to search through a massive range of candidate radii.
  • Bi-criteria Relaxation: To achieve sub-linear update times (times that don't grow linearly with the outlier budget $z$), the authors allow the algorithm to discard slightly more than $z$ outliers—specifically $(1+\epsilon)z$. This minor relaxation in the outlier budget yields massive gains in processing speed.
  • The Power of Bernoulli Sampling: In the dynamic setting, the authors use Bernoulli trials to decide if a newly inserted point should become a "representative." This maintains the correct statistical distribution across the layers without requiring constant re-sampling of the entire dataset.

Theoretical Guarantees and Optimality

As a theoretical computer science paper, the work focuses on rigorous mathematical proofs and complexity analysis applicable to any general metric space. The paper provides strong theoretical guarantees:

  • Efficiency: The main algorithm achieves an amortized update and query time of $\tilde{O}(k^2/\epsilon^4)$. Crucially, there is no $\Delta$ term in this complexity.
  • Quality: It guarantees a constant-factor approximation while discarding at most $(1+\epsilon)z$ outliers.
  • Faster Variant: Under the mild assumption that optimal clusters are relatively large (size $\Omega(z)$), the authors provide an accelerated version with $\tilde{O}(k^2/z)$ update and query time.
  • Optimality: They prove a lower bound of $\Omega(k^2/z)$ for any algorithm operating in this setting, demonstrating that their faster variant is essentially as fast as theoretically possible.

Limitations and Future Directions

The authors acknowledge a few necessary trade-offs in their approach. Removing the $\Delta$ dependence can lead to a larger constant factor in the approximation (the "tightness" of the clustering) compared to some $\Delta$-dependent methods. Additionally, the algorithm relies on a bi-criteria constraint: it must be allowed to discard $(1+\epsilon)z$ outliers to remain fast, meaning it cannot guarantee exactly $z$ outliers in sub-linear time.

Looking forward, the authors suggest extending this layered-sampling framework to other clustering objectives, such as $k$-median or $k$-means. They also propose exploring how these $\Delta$-independent algorithms could be adapted for Massively Parallel Computation (MPC) settings to handle even larger-scale datasets.

Summary updated

Abstract

In this paper, we study the fully dynamic k-center with outliers problem, where points are inserted and deleted over time and the goal is to maintain an approximate clustering while discarding up to z outliers. Existing algorithms typically rely on radius guessing to maintain cluster representations, leading to update and query times that depend explicitly on the aspect ratio Δ. We propose a layered-sampling framework that avoids radius guessing by maintaining a hierarchy of sampled structures, which can separate most inliers from potential outliers and refine the remaining uncertain points. The resulting algorithm achieves $\tilde{O}(k^2/\epsilon^4)$ update and query time independent of Δ, while guaranteeing a constant-factor approximation with $(1+\epsilon)z$ outliers discarded. Under mild assumptions, our result is complemented by a lower bound in metric space query model.
BibTeX
@inproceedings{huang2026new,
  author = {Junyu Huang and Zhize Li and Zhen Zhang and Xujia Li and Jianxin Wang and Qilong Feng},
  title = {{New Algorithms for Fully-Dynamic k-center with Outliers}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=RpjGh2J4Cw},
}
Figure