Improved Approximations for Distributed $k$-Center Clustering with Outliers and Fairness

Selecting representatives from distributed data requires geometric coverage, robustness to outliers, and control over group representation among the selected centers. We study $k$-center clustering with outliers and its fair extension, which imposes bounds on the number of centers selected from each of $g$ disjoint groups. We develop a two-round MapReduce framework for both problems in general metric spaces. The framework uses an unweighted summary that preserves $z+1$ nearby witnesses for every omitted point. Consequently, covering all but at most $z$ summary points allows coverage to be extended to the original dataset without increasing the outlier budget. For $k$-center with outliers, a greedy merging procedure achieves a $6$-approximation using $O(k(z+1)+z)$ point records per worker. For the fair extension, we additionally preserve nearby same-group candidates and combine LP-guided filtering with maximum-weight bipartite $b$-matching to obtain a first $11$-approximation using $O(k(z+g)+z)$ point records per worker. These factors hold when the optimal radius is supplied. By guessing the radius, our method yields $(6+\epsilon )$- and $(11+\epsilon )$-approximations, respectively, with the number of guesses charged explicitly in communication. Finally, we complement our theoretical results with experiments on six real-world datasets and a synthetic dataset with known optimal solutions, demonstrating substantial improvements in clustering utility over state-of-the-art methods.