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

Sayan Bandyapadhyay, Eden Chlamtáč, Zachary Friggstad, Mahya Jamshidian, Yury Makarychev, Ali Vakilian
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:4933-4941, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-bandyapadhyay26a, title = { A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering }, author = {Bandyapadhyay, Sayan and Chlamt{\'a}{\v{c}}, Eden and Friggstad, Zachary and Jamshidian, Mahya and Makarychev, Yury and Vakilian, Ali}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {4933--4941}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/bandyapadhyay26a/bandyapadhyay26a.pdf}, url = {https://proceedings.mlr.press/v300/bandyapadhyay26a.html}, abstract = { 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. } }
Endnote
%0 Conference Paper %T A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering %A Sayan Bandyapadhyay %A Eden Chlamtáč %A Zachary Friggstad %A Mahya Jamshidian %A Yury Makarychev %A Ali Vakilian %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-bandyapadhyay26a %I PMLR %P 4933--4941 %U https://proceedings.mlr.press/v300/bandyapadhyay26a.html %V 300 %X 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.
APA
Bandyapadhyay, S., Chlamtáč, E., Friggstad, Z., Jamshidian, M., Makarychev, Y. & Vakilian, A.. (2026). A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:4933-4941 Available from https://proceedings.mlr.press/v300/bandyapadhyay26a.html.

Related Material