New Algorithms for Fully-Dynamic k-center with Outliers

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.

Many real-world datasets are constantly changing: users join and leave online services, vehicles move through road networks, and sensors add new measurements. When we want to group such data into a fixed number of clusters, a few unusual points can pull the clusters in the wrong direction. We study how to keep useful clusters as points are inserted and deleted, while safely ignoring a limited number of outliers. Existing algorithms usually try many possible distance scales before deciding how large clusters should be. This can make them slow when the smallest and largest relevant distances in the data are very different. We propose a layered sampling method that repeatedly chooses representative points from the data that has not yet been covered, letting the data itself reveal the right scale instead of guessing it in advance. This gives an algorithm whose update and query times do not depend on that distance gap, while still producing clusters close to the best possible solution and discarding only slightly more than the target number of outliers. We also provide a faster version under a natural cluster-size condition and prove a matching lower bound, showing that this improvement is close to the best one can hope for.