# Constant-Factor Approximation Algorithms for Socially Fair k-Clustering

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

## Key facts

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

## Builds on (most cited first, 22 of 22)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [50 Years of Test (Un)fairness: Lessons for Machine Learning](https://mlsanity.com/paper/1811.10104/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [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)
- [Racial categories in machine learning](https://mlsanity.com/paper/1811.11668/) (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)
- [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)
- [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)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [A Technique for Obtaining True Approximations for k-Center with Covering Constraints](https://mlsanity.com/paper/2007.03946/) (2020)
- [Fair Colorful k-Center Clustering](https://mlsanity.com/paper/2007.04059/) (2020)
- [New Approximability Results for the Robust k-Median Problem](https://mlsanity.com/paper/1309.4602/) (2013)
- [Structural Iterative Rounding for Generalized k-Median Problems](https://mlsanity.com/paper/2009.00808/) (2020)

## Built on by (most cited first, 8 of 8)

- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Approximately Optimal Core Shapes for Tensor Decompositions](https://mlsanity.com/paper/2302.03886/) (2023)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [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)
- [Socially Fair Center-based and Linear Subspace Clustering](https://mlsanity.com/paper/2208.10095/) (2022)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)

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