# Improved Streaming Algorithm for Fair k-Center Clustering

arXiv: https://arxiv.org/abs/2510.05937 · HTML: https://mlsanity.com/paper/2510.05937/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2025.

## Built on by (most cited first, 2 of 2)

- [Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means](https://mlsanity.com/paper/2604.16061/) (2026)
- [Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering](https://mlsanity.com/paper/2609.06384/) (2026)

## Abstract (arXiv)

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 λ-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(klog 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.