A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering

In this work, we study pairwise fair clustering with ≥ 2 groups, where for every cluster C and every group i ∈ [], the number of points in C from group i must be at most t times the number of points in C from any other group j ∈ [], for a given integer t. To the best of our knowledge, only bi-criteria approximation and exponential-time algorithms follow for this problem from the prior work on fair clustering problems when > 2. In our work, focusing on the > 2 case, we design the first polynomial-time (t^· · k)O()-approximation for this problem with k-median cost that does not violate the fairness constraints. We complement our algorithmic result by providing hardness of approximation results, which show that our problem even when =2 is almost as hard as the popular uniform capacitated k-median, for which no polynomial-time algorithm with an approximation factor of o(log k) is known.