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 (k) is known.