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

Abstract

In this work, we study pairwise fair k-Median 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. Only bi-criteria approximation and exponential-time algorithms follow for this problem from the prior work on fair clustering problems when ℓ > 2. We present the first polynomial-time O(k^2·ℓ· t)-approximation for this problem that does not violate the fairness constraints. We also implemented our algorithm on a variety of datasets to test the “price of fairness" achieved by our approach in real data, which turned out to be significantly smaller than the theoretical guarantee.