# Tight FPT Approximation for Socially Fair Clustering

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 33 references that are in the map.
- First posted on arXiv 12 Jun 2021.

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

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (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)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [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)
- [Faster Algorithms for the Constrained k-means Problem](https://mlsanity.com/paper/1504.02564/) (2015)
- [A Unified Framework for Clustering Constrained Data without Locality Property](https://mlsanity.com/paper/1810.01049/) (2018)
- [Tight FPT Approximations for k-Median and k-Means](https://mlsanity.com/paper/1904.12334/) (2019)
- [Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)](https://mlsanity.com/paper/1910.11850/) (2019)
- [On Uniform Capacitated k-Median Beyond the Natural LP Relaxation](https://mlsanity.com/paper/1409.6739/) (2014)
- [FPT Approximation for Constrained Metric k-Median/Means](https://mlsanity.com/paper/2007.11773/) (2020)
- [A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median](https://mlsanity.com/paper/1307.2808/) (2013)

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

- [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)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [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)
- [Fair Clustering: A Causal Perspective](https://mlsanity.com/paper/2312.09061/) (2023)
- [Fair Minimum Representation Clustering](https://mlsanity.com/paper/2302.03151/) (2023)
- [Fair Clustering with Minimum Representation Constraints](https://mlsanity.com/paper/2409.02963/) (2024)
- [Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity](https://mlsanity.com/paper/2512.03718/) (2025)
- [UniFair: A unified fair clustering approach based on separation and compactness](https://mlsanity.com/paper/2606.04777/) (2026)

## Abstract (arXiv)

In this work, we study the socially fair k-median/k-means problem. We are given a set of points P in a metric space X with a distance function d(.,.). There are ℓ groups: P1,dotsc,Pℓ subseteq P. We are also given a set F of feasible centers in X. The goal in the socially fair k-median problem is to find a set C subseteq F of k centers that minimizes the maximum average cost over all the groups. That is, find C that minimizes the objective function Phi(C,P) equiv maxj Big sumx ∈ Pj d(C,x)/|Pj| Big, where d(C,x) is the distance of x to the closest center in C. The socially fair k-means problem is defined similarly by using squared distances, i.e., d2(.,.) instead of d(.,.). The current best approximation guarantee for both the problems is Oleft( fraclog ℓlog log ℓ right) due to Makarychev and Vakilian [COLT 2021]. In this work, we study the fixed parameter tractability of the problems with respect to parameter k. We design (3+varepsilon) and (9 + varepsilon) approximation algorithms for the socially fair k-median and k-means problems, respectively, in FPT (fixed parameter tractable) time f(k,varepsilon) · nO(1), where f(k,varepsilon) = (k/varepsilon)^O(k) and n = |P cup F|. Furthermore, we show that if Gap-ETH holds, then better approximation guarantees are not possible in FPT time.