New Algorithms for Fully-Dynamic k-center with Outliers

摘要

In this paper, we study the fully-dynamic k-center with outliers problem. In this setting, the clustering data changes over time through a sequence of updates. The goal is to maintain an approximate k-center solution with efficient update and query time, while allowing up to z points to be discarded as outliers. To achieve provable guarantees, existing approaches typically rely on radius-guessing to maintain clusters with a uniform radius associated with the optimal one. Although effective, these methods can yield additional update overhead to maintain pairwise distance bounds, and the update and query time typically have explicit dependence on the aspect ratio Δ (the ratio of the maximum to the minimum pairwise distance). This may limit the scalability of the algorithms in large-aspect-ratio settings. To address these issues, we propose a layered-sampling method that can achieve sub-linear update and query time while eliminating prior knowledge and assumptions on aspect ratio terms. The proposed method avoids traditional radius guessing process by constructing layered structures in different stages, where the initial layers summarize most inliers, the transition layer finds good representatives for the remaining points, and the final layers carefully adjusts the outliers discarded using a fine-grained division manner. By adopting an update-delay strategy, the proposed algorithm achieves $\tilde{O}(k^2/\epsilon^4)$ update time and $\tilde{O}(k^2/\epsilon^4)$ query time that are independent of Δ, while guaranteeing constant approximation with at most $(1+\epsilon)z$ outliers discarded. Under mild assumptions on optimal cluster sizes, the time bounds can further be improved by a factor of $z$ via sampling-based data reduction techniques. This is complemented with a lower bound update time of $\Omega(k^2/z)$ in the general metric space query model.