Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering

Fairness in clustering has attracted sustained research interest, motivated by the need to ensure equitable representation of protected groups in machine learning applications. We study fair $k$-means clustering in Euclidean space, where the proportion of each protected group in every cluster must lie within specified lower and upper bounds. These constraints make it challenging to determine both cluster centers and point assignments. Our algorithm first splits the input into many small fair clusters and then merges them into $k$ clusters with a weighted $k$-means algorithm. The merge is cheap only when the small clusters do not move points away from their optimal centers, so we add a displacement penalty to the split, which charges each point for how far the small clusters move it. Given a $ρ$-approximate algorithm for weighted $k$-means and any $ε>0$, our algorithm returns a fractional solution whose cost is at most $3ρ+ε$ times the optimal integral fair cost. With a PTAS as the subroutine, the approximation ratio becomes $3+O(ε)$, improving the previous factor of $5+O(ε)$. This ratio is the best possible: unless P=NP, no polynomial-time algorithm achieves the ratio $3-δ$ for any fixed $δ>0$, even in one dimension. The solution satisfies all fairness constraints exactly and can be rounded to an integral assignment with a bounded additive violation of fairness and no increase in cost. The same approximation guarantee extends to the $k$-sparse Wasserstein barycenter problem.

We study discrete k-clustering problems in general metric spaces that are constrained by a combination of two different fairness conditions within the demographic fairness model. Given a metric space (P,d), where every point in P is equipped with a protected attribute, and a number k, the goal is to partition P into k clusters with a designated center each, such that a center-based objective function is minimized and the attributes are fairly distributed with respect to the following two fairness concepts: 1) group fairness: We aim for clusters with balanced numbers of attributes by specifying lower and upper bounds for the desired attribute proportions. 2) diverse center selection: Clusters have natural representatives, i.e., their centers. We ask for a balanced set of representatives by specifying the desired number of centers to choose from each attribute. Dickerson, Esmaeili, Morgenstern and Zhang (2023) denote the combination of these two constraints as doubly constrained fair clustering. They present algorithms whose guarantees depend on the best known approximation factors for either of these problems. Currently, this implies an 8-approximation with a small additive violation on the group fairness constraint. For k-center, we improve this approximation factor to 4 with a small additive violation. This guarantee also depends on the currently best algorithm for DS-fair k-center given by Jones, Nguyen and Nguyen (2020). For k-median and k-means, we propose the first constant-factor approximation algorithms. Our algorithms transform a solution that satisfies diverse center selection into a doubly constrained fair clustering using an LP-based approach. Furthermore, our results are generalizable to other center-selection constraints, such as matroid k-clustering and knapsack constraints.

In this work, we study the hardness of approximation of the fair $k$-center problem. In this problem, we are given a set of data points in a metric space that is partitioned into groups and the task is to choose a subset of $k$-data points, called centers, such that a prescribed number of data points from each group are chosen while minimizing the maximum distance from any point to its closest center. Although a polynomial-time $3$-approximation is known for fair $k$-center in general metrics, it has remained open whether this approximation guarantee is tight or could be further improved, especially since the classical unconstrained $k$-center problem admits a polynomial-time factor-$2$ approximation. We resolve this open question by proving that, assuming $\mathsf{P} \neq \mathsf{NP}$, for any $ε>0$, no polynomial-time algorithm can approximate fair $k$-center to $(3-ε)$-factor. Our inapproximability results hold even when only two disjoint groups are present and at least one center must be chosen from each group. Further, it extends to the canonical one-per-group setting with $k$-groups (for arbitrary $k$), where exactly one center must be selected from each group. Consequently, the factor-$3$ barrier for fair $k$-center in general metric spaces is inherent, and existing $3$-approximation algorithms are optimal up to lower-order terms even in these restricted regimes. This result stands in sharp contrast to the $k$-supplier formulation, where both the unconstrained and fair variants admit factor-$3$ approximation in polynomial time.