New Algorithms for Fully-Dynamic k-center with Outliers

Junyu Huang, Zhize Li, Zhen Zhang, Xujia Li, Jianxin Wang, Qilong Feng
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:47020-47053, 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 $\Delta$. 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 $\Delta$, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-huang26ab, title = {New Algorithms for Fully-Dynamic k-center with Outliers}, author = {Huang, Junyu and Li, Zhize and Zhang, Zhen and Li, Xujia and Wang, Jianxin and Feng, Qilong}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {47020--47053}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/huang26ab/huang26ab.pdf}, url = {https://proceedings.mlr.press/v306/huang26ab.html}, 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 $\Delta$. 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 $\Delta$, 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.} }
Endnote
%0 Conference Paper %T New Algorithms for Fully-Dynamic k-center with Outliers %A Junyu Huang %A Zhize Li %A Zhen Zhang %A Xujia Li %A Jianxin Wang %A Qilong Feng %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-huang26ab %I PMLR %P 47020--47053 %U https://proceedings.mlr.press/v306/huang26ab.html %V 306 %X 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 $\Delta$. 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 $\Delta$, 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.
APA
Huang, J., Li, Z., Zhang, Z., Li, X., Wang, J. & Feng, Q.. (2026). New Algorithms for Fully-Dynamic k-center with Outliers. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:47020-47053 Available from https://proceedings.mlr.press/v306/huang26ab.html.

Related Material