# Fair k-Center Clustering for Data Summarization

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

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jan 2019.

## Built on by (most cited first, 30 of 65)

- [The Hidden Uniform Cluster Prior in Self-Supervised Learning](https://mlsanity.com/paper/2210.07277/) (2022)
- [Evaluating Fairness of Machine Learning Models Under Uncertain and Incomplete Information](https://mlsanity.com/paper/2102.08410/) (2021)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Deep Fair Clustering via Maximizing and Minimizing Mutual Information: Theory, Algorithm and Metric](https://mlsanity.com/paper/2209.12396/) (2022)
- [Near-Optimal Explainable k-Means for All Dimensions](https://mlsanity.com/paper/2106.15566/) (2021)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [Robust Fair Clustering: A Novel Fairness Attack and Defense Framework](https://mlsanity.com/paper/2210.01953/) (2022)
- [Deep Fair Discriminative Clustering](https://mlsanity.com/paper/2105.14146/) (2021)
- [A Stochastic Alternating Balance k-Means Algorithm for Fair Clustering](https://mlsanity.com/paper/2105.14172/) (2021)
- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [Fairness-aware Model-agnostic Positive and Unlabeled Learning](https://mlsanity.com/paper/2206.09346/) (2022)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Multiple-criteria Based Active Learning with Fixed-size Determinantal Point Processes](https://mlsanity.com/paper/2107.01622/) (2021)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Constant-Factor Approximation Algorithms for Socially Fair k-Clustering](https://mlsanity.com/paper/2206.11210/) (2022)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [R3-NL2GQL: A Model Coordination and Knowledge Graph Alignment Approach for NL2GQL](https://mlsanity.com/paper/2311.01862/) (2023)
- [Pairwise Fairness for Ordinal Regression](https://mlsanity.com/paper/2105.03153/) (2021)
- [Improved Approximation for Fair Correlation Clustering](https://mlsanity.com/paper/2206.05050/) (2022)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Emergent specialization from participation dynamics and multi-learner retraining](https://mlsanity.com/paper/2206.02667/) (2022)
- [Learning to Generate Fair Clusters from Demonstrations](https://mlsanity.com/paper/2102.03977/) (2021)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [Feature-based Individual Fairness in k-Clustering](https://mlsanity.com/paper/2109.04554/) (2021)
- [Fair Representation Clustering with Several Protected Classes](https://mlsanity.com/paper/2202.01391/) (2022)
- [Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost](https://mlsanity.com/paper/2205.14198/) (2022)

## Abstract (arXiv)

In data summarization we want to choose k prototypes in order to summarize a data set. We study a setting where the data set comprises several demographic groups and we are restricted to choose ki prototypes belonging to group i. A common approach to the problem without the fairness constraint is to optimize a centroid-based clustering objective such as k-center. A natural extension then is to incorporate the fairness constraint into the clustering problem. Existing algorithms for doing so run in time super-quadratic in the size of the data set, which is in contrast to the standard k-center problem being approximable in linear time. In this paper, we resolve this gap by providing a simple approximation algorithm for the k-center problem under the fairness constraint with running time linear in the size of the data set and k. If the number of demographic groups is small, the approximation guarantee of our algorithm only incurs a constant-factor overhead.