# KFC: A Scalable Approximation Algorithm for k-center Fair Clustering

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2020.

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

- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Robust Fair Clustering: A Novel Fairness Attack and Defense Framework](https://mlsanity.com/paper/2210.01953/) (2022)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Tight FPT Approximation for Constrained k-Center and k-Supplier](https://mlsanity.com/paper/2110.14242/) (2021)
- [Fair Clustering via Alignment](https://mlsanity.com/paper/2505.09131/) (2025)
- [Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means](https://mlsanity.com/paper/2604.16061/) (2026)
- [Approximating Fair k-Min-Sum-Radii in Euclidean Space](https://mlsanity.com/paper/2309.00834/) (2023)
- [Fair Clustering with Minimum Representation Constraints](https://mlsanity.com/paper/2409.02963/) (2024)
- [Fair Bayesian Model-Based Clustering](https://mlsanity.com/paper/2506.12839/) (2025)
- [Fair Model-based Clustering](https://mlsanity.com/paper/2602.21509/) (2026)

## Abstract (arXiv)

In this paper, we study the problem of fair clustering on the k-center objective. In fair clustering, the input is N points, each belonging to at least one of l protected groups, e.g. male, female, Asian, Hispanic. The objective is to cluster the N points into k clusters to minimize a classical clustering objective function. However, there is an additional constraint that each cluster needs to be fair, under some notion of fairness. This ensures that no group is either "over-represented" or "under-represented" in any cluster. Our work builds on the work of Chierichetti et al. (NIPS 2017), Bera et al. (NeurIPS 2019), Ahmadian et al. (KDD 2019), and Bercea et al. (APPROX 2019). We obtain a randomized 3-approximation algorithm for the k-center objective function, beating the previous state of the art (4-approximation). We test our algorithm on real datasets, and show that our algorithm is effective in finding good clusters without over-representation or under-representation, surpassing the current state of the art in runtime speed, clustering cost, while achieving similar fairness violations.