Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

7-2026

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 Õ(k²/ε⁴) update and query time independent of Δ, while guaranteeing a constant-factor approximation with (1+ε)z outliers discarded. Under mild assumptions, our result is complemented by a lower bound in metric space query model.

Keywords

fully-dynamic clustering, clustering with outliers, k-center clustering

Discipline

Artificial Intelligence and Robotics

Research Areas

Data Science and Engineering; Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

Proceedings of the 43rd International Conference on Machine Learning (ICML 2026), Seoul, South Korea, July 6-11

Volume

306

First Page

47020

Last Page

47053

Publisher

Proceedings of Machine Learning Research

City or Country

Seoul, South Korea

Download

Share

COinS