other · Underline Science Inc. · 2026
Improved Streaming Algorithm for Fair k-Center Clustering
Association for Artificial Intelligence 2026, Chao Chen, Longkun Guo, Chaoqi Jia, Zeyu Lin
Cited by 0Open access
Abstract
Many real-world applications pose challenges in incorporating fairness constraints into the $k$-center clustering problem, where the dataset consists of $m$ demographic groups, each with a specified upper bound on the number of centers to ensure fairness. Focusing on big data scenarios, this paper addresses the problem in a streaming setting, where data points arrive one by one sequentially in a continuous stream. Leveraging a structure called the $\lambda$-independent center set, we propose a one-pass streaming algorithm that first computes a reserved set of points during the streaming process. Then, for the post-streaming process, we propose an approach for selecting centers from the reserved point set by analyzing all three possible cases, transforming the most complicated one into a specially constrained vertex cover problem in an auxiliary graph. Our algorithm achieves a tight approximation ratio of 5 while consuming $O(k\log n)$ memory. It can also be readily adapted to solve the offline fair $k$-center problem, achieving a 3-approximation ratio that matches the current state of the art. Furthermore, we extend our approach to a semi-structured data stream, where data points from each group arrive in batches. In this setting, we present a 3-approximation algorithm for $m = 2$ and a 4-approximation algorithm for general $m$. Lastly, we conduct extensive experiments to evaluate the performance of our approaches, demonstrating that they outperform existing baselines in both clustering cost and runtime efficiency.
Cite this paper
2026, A. F. A. I., Chen, C., Guo, L., Jia, C., & Lin, Z. (2026). Improved Streaming Algorithm for Fair k-Center Clustering. Underline Science Inc.. https://doi.org/10.48448/kex8-gk92
2026, Association for Artificial Intelligence, et al. “Improved Streaming Algorithm for Fair k-Center Clustering.” Underline Science Inc., 2026, https://doi.org/10.48448/kex8-gk92.
2026, Association for Artificial Intelligence, Chao Chen, Longkun Guo, Chaoqi Jia, and Zeyu Lin. 2026. “Improved Streaming Algorithm for Fair k-Center Clustering.” Underline Science Inc.. https://doi.org/10.48448/kex8-gk92.
2026, A.F.A.I. et al. (2026) ‘Improved Streaming Algorithm for Fair k-Center Clustering’, Underline Science Inc.. Available at: https://doi.org/10.48448/kex8-gk92.
@misc{20262026improved,
title = {{Improved Streaming Algorithm for Fair k-Center Clustering}},
author = {2026, Association for Artificial Intelligence and Chen, Chao and Guo, Longkun and Jia, Chaoqi and Lin, Zeyu},
journal = {Underline Science Inc.},
year = {2026},
doi = {10.48448/kex8-gk92}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.