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

arXiv: https://arxiv.org/abs/2405.10378 · HTML: https://mlsanity.com/paper/2405.10378/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 48 references that are in the map.
- First posted on arXiv 16 May 2024.

## Builds on (most cited first, 30 of 35)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [A Center in Your Neighborhood: Fairness in Facility Location](https://mlsanity.com/paper/1908.09041/) (2019)
- [A Pairwise Fair and Community-preserving Approach to k-Center Clustering](https://mlsanity.com/paper/2007.07384/) (2020)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications](https://mlsanity.com/paper/2007.10137/) (2020)
- [Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints](https://mlsanity.com/paper/2103.02013/) (2021)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [How to Solve Fair k-Center in Massive Data Models](https://mlsanity.com/paper/2002.07682/) (2020)
- [Matroid and Knapsack Center Problems](https://mlsanity.com/paper/1301.0745/) (2013)
- [A Technique for Obtaining True Approximations for k-Center with Covering Constraints](https://mlsanity.com/paper/2007.03946/) (2020)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Fair Clustering with Multiple Colors](https://mlsanity.com/paper/2002.07892/) (2020)
- [Fair Colorful k-Center Clustering](https://mlsanity.com/paper/2007.04059/) (2020)
- [Which Lp norm is the fairest? Approximations for fair facility location across all "p"](https://mlsanity.com/paper/2211.14873/) (2022)
- [Constant-Factor Approximation Algorithms for Socially Fair k-Clustering](https://mlsanity.com/paper/2206.11210/) (2022)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [A Constant Approximation for Colorful k-Center](https://mlsanity.com/paper/1907.08906/) (2019)
- [On Uniform Capacitated k-Median Beyond the Natural LP Relaxation](https://mlsanity.com/paper/1409.6739/) (2014)

## Abstract (arXiv)

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(k2· ℓ · 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(log k) is known.