mlsanityData to 7 Oct 2026

Approximation Algorithms for Socially Fair Clustering

arXiv 2103.02512 ↗First posted 3 Mar 2021cs.DS cs.LG stat.MLcited by 25

Not on the map. Why?

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].

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 29 of its 45 references that are in the map. First posted on arXiv 3 Mar 2021.

Builds on

29 of 45 references.

References · 29

  1. 2016Equality of Opportunity in Supervised Learningcited by 2,000
  2. 2014Certifying and removing disparate impactcited by 715
  3. 2016Fair prediction with disparate impact: A study of bias in recidivism prediction instrumentscited by 671
  4. 2016Inherent Trade-Offs in the Fair Determination of Risk Scorescited by 582
  5. 2018Fair Clustering Through Fairletscited by 176
  6. 2018The Frontiers of Fairness in Machine Learningcited by 139
  7. 2019Fair Algorithms for Clusteringcited by 98
  8. 2019Scalable Fair Clusteringcited by 78
  9. 2019Proportionally Fair Clusteringcited by 69
  10. 2019Fair k-Center Clustering for Data Summarizationcited by 65
  11. 2020Individual Fairness for k-Clusteringcited by 56
  12. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
17 more
  1. 2019Coresets for Clustering with Fairness Constraintscited by 51
  2. 2019Clustering without Over-Representationcited by 50
  3. 2018On the cost of essentially fair clusteringscited by 44
  4. 2020Fair clustering via equitable group representationscited by 43
  5. 2019A Center in Your Neighborhood: Fairness in Facility Locationcited by 26
  6. 2020A Pairwise Fair and Community-preserving Approach to k-Center Clusteringcited by 26
  7. 2017Constant Approximation for k-Median and k-Means with Outliers via Iterative Roundingcited by 25
  8. 2019Fairness in Clustering with Multiple Sensitive Attributescited by 20
  9. 2020A Notion of Individual Fairness for Clusteringcited by 20
  10. 2020Distributional Individual Fairness in Clusteringcited by 14
  11. 2020How to Solve Fair k-Center in Massive Data Modelscited by 12
  12. 2013Matroid and Knapsack Center Problemscited by 11
  13. 2018Approximation Algorithms for Minimum Norm and Ordered Optimization Problemscited by 11
  14. 2019Near Neighbor: Who is the Fairest of Them All?cited by 7
  15. 2013New Approximability Results for the Robust k-Median Problemcited by 6
  16. 2019Fair Near Neighbor Search: Independent Range Sampling in High Dimensionscited by 5
  17. 2021Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?cited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 6; 2023: 6; 2024: 7; 2025: 1; 2026: 1.

25 papers.

Sort:

  1. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  2. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  3. 2021Tight FPT Approximation for Socially Fair Clusteringcited by 10
  4. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  5. 2022Constant-Factor Approximation Algorithms for Socially Fair k-Clusteringcited by 8
  6. 2022Individual Preference Stability for Clusteringcited by 8
  7. 2024A Scalable Algorithm for Individually Fair K-means Clusteringcited by 8
  8. 2021Efficient Algorithms For Fair Clustering with a New Fairness Notioncited by 5
  9. 2023Parameterized Approximation Schemes for Clustering with General Norm Objectivescited by 5
  10. 2022Fair Representation Clustering with Several Protected Classescited by 4
  11. 2024Minimax Group Fairness in Strategic Classificationcited by 4
  12. 2023Spectral Normalized-Cut Graph Partitioning with Fairness Constraintscited by 3
13 more
  1. 2022Balancing Utility and Fairness in Submodular Maximization (Technical Report)cited by 2
  2. 2023Parameterized Approximation for Robust Clustering in Discrete Geometric Spacescited by 2
  3. 2024On Socially Fair Low-Rank Approximation and Column Subset Selectioncited by 2
  4. 2022Measuring and mitigating voting access disparities: a study of race and polling locations in Florida and North Carolinacited by 1
  5. 2022Socially Fair Center-based and Linear Subspace Clusteringcited by 1
  6. 2023Fair Clustering: A Causal Perspectivecited by 1
  7. 2024Scalable Algorithms for Individual Preference Stable Clusteringcited by 1
  8. 2024Fair Clustering: Critique, Caveats, and Future Directionscited by 1
  9. 2023Fair Minimum Representation Clusteringcited by 0
  10. 2024A Polynomial-Time Approximation for Pairwise Fair k-Median Clusteringcited by 0
  11. 2024Fair Clustering with Minimum Representation Constraintscited by 0
  12. 2025Welfare-Centric Clusteringcited by 0
  13. 2026UniFair: A unified fair clustering approach based on separation and compactnesscited by 0