# Approximation Algorithms for Socially Fair Clustering arXiv: https://arxiv.org/abs/2103.02512 · HTML: https://mlsanity.com/paper/2103.02512/ ## Key facts - Cited by 25 papers in the map (data through 14 Oct 2026). - Builds on 29 of its 45 references that are in the map. - First posted on arXiv 3 Mar 2021. ## Builds on (most cited first, 29 of 29) - [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016) - [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014) - [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016) - [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016) - [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018) - [The Frontiers of Fairness in Machine Learning](https://mlsanity.com/paper/1810.08810/) (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) - [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018) - [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019) - [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) - [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) - [Fairness in Clustering with Multiple Sensitive Attributes](https://mlsanity.com/paper/1910.05113/) (2019) - [A Notion of Individual Fairness for Clustering](https://mlsanity.com/paper/2006.04960/) (2020) - [Distributional Individual Fairness in Clustering](https://mlsanity.com/paper/2006.12589/) (2020) - [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) - [Approximation Algorithms for Minimum Norm and Ordered Optimization Problems](https://mlsanity.com/paper/1811.05022/) (2018) - [Near Neighbor: Who is the Fairest of Them All?](https://mlsanity.com/paper/1906.02640/) (2019) - [New Approximability Results for the Robust k-Median Problem](https://mlsanity.com/paper/1309.4602/) (2013) - [Fair Near Neighbor Search: Independent Range Sampling in High Dimensions](https://mlsanity.com/paper/1906.01859/) (2019) - [Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?](https://mlsanity.com/paper/2101.10905/) (2021) ## Built on by (most cited first, 25 of 25) - [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021) - [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021) - [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021) - [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023) - [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 Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024) - [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021) - [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023) - [Fair Representation Clustering with Several Protected Classes](https://mlsanity.com/paper/2202.01391/) (2022) - [Minimax Group Fairness in Strategic Classification](https://mlsanity.com/paper/2410.02513/) (2024) - [Spectral Normalized-Cut Graph Partitioning with Fairness Constraints](https://mlsanity.com/paper/2307.12065/) (2023) - [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022) - [Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces](https://mlsanity.com/paper/2305.07316/) (2023) - [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024) - [Measuring and mitigating voting access disparities: a study of race and polling locations in Florida and North Carolina](https://mlsanity.com/paper/2205.14867/) (2022) - [Socially Fair Center-based and Linear Subspace Clustering](https://mlsanity.com/paper/2208.10095/) (2022) - [Fair Clustering: A Causal Perspective](https://mlsanity.com/paper/2312.09061/) (2023) - [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024) - [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024) - [Fair Minimum Representation Clustering](https://mlsanity.com/paper/2302.03151/) (2023) - [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024) - [Fair Clustering with Minimum Representation Constraints](https://mlsanity.com/paper/2409.02963/) (2024) - [Welfare-Centric Clustering](https://mlsanity.com/paper/2508.10345/) (2025) - [UniFair: A unified fair clustering approach based on separation and compactness](https://mlsanity.com/paper/2606.04777/) (2026) ## Abstract (arXiv) We present an (eO(p) fraclog ℓloglogℓ)-approximation algorithm for socially fair clustering with the ℓp-objective. In this problem, we are given a set of points in a metric space. Each point belongs to one (or several) of ℓ groups. The goal is to find a k-medians, k-means, or, more generally, ℓp-clustering that is simultaneously good for all of the groups. More precisely, we need to find a set of k centers C so as to minimize the maximum over all groups j of sumu in group j d(u,C)p. The socially fair clustering problem was independently proposed by Ghadiri, Samadi, and Vempala [2021] and Abbasi, Bhaskara, and Venkatasubramanian [2021]. Our algorithm improves and generalizes their O(ℓ)-approximation algorithms for the problem. The natural LP relaxation for the problem has an integrality gap of Omega(ℓ). In order to obtain our result, we introduce a strengthened LP relaxation and show that it has an integrality gap of Theta(fraclog ℓloglogℓ) for a fixed p. Additionally, we present a bicriteria approximation algorithm, which generalizes the bicriteria approximation of Abbasi et al. [2021].