mlsanityData to 7 Oct 2026

Constant-Factor Approximation Algorithms for Socially Fair k-Clustering

arXiv 2206.11210 ↗First posted 22 Jun 2022cs.DS cs.AI cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

We study approximation algorithms for the socially fair (ℓp, k)-clustering problem with m groups, whose special cases include the socially fair k-median (p=1) and socially fair k-means (p=2) problems. We present (1) a polynomial-time (5+2√6)p-approximation with at most k+m centers (2) a (5+2√6+ε)p-approximation with k centers in time n^2O(p)· m2, and (3) a (15+6√6)p approximation with k centers in time km·poly(n). The first result is obtained via a refinement of the iterative rounding method using a sequence of linear programs. The latter two results are obtained by converting a solution with up to k+m centers to one with k centers using sparsification methods for (2) and via an exhaustive search for (3). We also compare the performance of our algorithms with existing bicriteria algorithms as well as exactly k center approximation algorithms on benchmark datasets, and find that our algorithms also outperform existing methods in practice.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 22 of its 46 references that are in the map. First posted on arXiv 22 Jun 2022.

Builds on

22 of 46 references.

References · 22

  1. 2018Fair Clustering Through Fairletscited by 176
  2. 201850 Years of Test (Un)fairness: Lessons for Machine Learningcited by 101
  3. 2019Fair Algorithms for Clusteringcited by 98
  4. 2019Proportionally Fair Clusteringcited by 69
  5. 2018The Price of Fair PCA: One Extra Dimensioncited by 67
  6. 2019Fair k-Center Clustering for Data Summarizationcited by 65
  7. 2020Individual Fairness for k-Clusteringcited by 56
  8. 2019Clustering without Over-Representationcited by 50
  9. 2018Racial categories in machine learningcited by 48
  10. 2020Fair clustering via equitable group representationscited by 43
  11. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  12. 2019A Center in Your Neighborhood: Fairness in Facility Locationcited by 26
10 more
  1. 2020A Pairwise Fair and Community-preserving Approach to k-Center Clusteringcited by 26
  2. 2017Constant Approximation for k-Median and k-Means with Outliers via Iterative Roundingcited by 25
  3. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  4. 2019Fairness in Clustering with Multiple Sensitive Attributescited by 20
  5. 2020A Notion of Individual Fairness for Clusteringcited by 20
  6. 2021A New Notion of Individually Fair Clustering: α-Equitable k-Centercited by 18
  7. 2020A Technique for Obtaining True Approximations for k-Center with Covering Constraintscited by 11
  8. 2020Fair Colorful k-Center Clusteringcited by 9
  9. 2013New Approximability Results for the Robust k-Median Problemcited by 6
  10. 2020Structural Iterative Rounding for Generalized k-Median Problemscited by 4

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 4; 2024: 3.

8 papers.

  1. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  2. 2023Approximately Optimal Core Shapes for Tensor Decompositionscited by 8
  3. 2023Parameterized Approximation Schemes for Clustering with General Norm Objectivescited by 5
  4. 2023Parameterized Approximation for Robust Clustering in Discrete Geometric Spacescited by 2
  5. 2024On Socially Fair Low-Rank Approximation and Column Subset Selectioncited by 2
  6. 2022Socially Fair Center-based and Linear Subspace Clusteringcited by 1
  7. 2024Scalable Algorithms for Individual Preference Stable Clusteringcited by 1
  8. 2024A Polynomial-Time Approximation for Pairwise Fair k-Median Clusteringcited by 0