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

Abstract

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 O(k^2 t)-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.

Tasks

Reproductions