Skip to content
conftrace_
2026 AISTATS AISTATS 2026

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

In this work, we study pairwise fair $k$-Median with $\ell \ge 2$ groups, where for every cluster $C$ and every group $i \in [\ell]$, 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 \in [\ell]$, 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 $\ell > 2$. We present the first polynomial-time $O(k^2\cdot \ell \cdot 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.

More from AISTATS 2026

All AISTATS 2026 papers →