Improved Approximation Algorithms for Euclidean Fair $k$-Center Clustering

Let $S$ be a set of points partitioned into $m$ demographic groups. Given an upper bound $k_{\ell }$ on the number of centers that can be chosen from each group $\ell$, the fair $k$-center problem asks for a set of centers $C$ that satisfies these fairness constraints while minimizing the maximum distance from any point to its nearest center. In this paper, we first present a randomized algorithm for the Euclidean setting that achieves an approximation ratio of $1+\sqrt{3}\approx 2.732$, thereby breaking the factor-$3$ barrier known for general metrics. The key idea is to reduce the problem to a generalized exact matching problem on a carefully designed auxiliary graph, which can then be solved using a generalized exact matching algorithm. For the case $m=2$, we then develop a deterministic algorithm with the same approximation ratio and improved running time. This algorithm exploits the geometric structure of the Euclidean setting, allowing us to use maximum matching rather than exact matching. To the best of our knowledge, this is the first approximation ratio strictly below $3$ for Euclidean fair $k$-center, suggesting that fair $k$-center admits better approximation guarantees in Euclidean spaces. Finally, we complement our theoretical results with experiments on five real-world datasets and one synthetic dataset with known optimal solutions, demonstrating the improvements in clustering utility over state-of-the-art methods.