Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering

Abstract

Motivated by the growing importance of fairness in machine learning, fair $k$-center clustering has attracted considerable research attention as a fundamental problem. In this problem, a dataset is partitioned into $m$ disjoint groups, and the objective is to select $k$ data points as centers, subject to upper bounds on the number of centers chosen from each group, so as to minimize the maximum distance between any data point and its assigned center. Focusing on Euclidean spaces, which are ubiquitous in machine learning applications, we first develop a parameterized approximation algorithm for Euclidean fair $k$-center with an approximation ratio of $2.732$. By incorporating this algorithm as a post-processing stage into a one-pass streaming framework for large-scale data, we obtain an approximation ratio of $4.464$. These ratios can be further improved to $2.414$ and $3.828$, respectively. To ensure polynomial-time complexity, we further design a one-pass streaming algorithm with approximation ratio of $4.732$, improving upon the state-of-the-art ratio of $5$ for general metric spaces and demonstrating that the streaming fair $k$-center problem admits better approximations in Euclidean spaces than in general metrics. Finally, extensive experiments show that our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.