# Diversity-aware k-median : Clustering with fair center representation

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2021.

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

- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [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)
- [Spectral Normalized-Cut Graph Partitioning with Fairness Constraints](https://mlsanity.com/paper/2307.12065/) (2023)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights](https://mlsanity.com/paper/2410.12913/) (2024)
- [Adversarial Fair Multi-View Clustering](https://mlsanity.com/paper/2508.04071/) (2025)
- [Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means](https://mlsanity.com/paper/2604.16061/) (2026)
- [Fair Minimum Representation Clustering](https://mlsanity.com/paper/2302.03151/) (2023)
- [Fair Clustering with Minimum Representation Constraints](https://mlsanity.com/paper/2409.02963/) (2024)
- [FACROC: a fairness measure for FAir Clustering through ROC curves](https://mlsanity.com/paper/2503.00854/) (2025)
- [Interpretable Fair Clustering](https://mlsanity.com/paper/2511.21109/) (2025)
- [On the Hardness of Approximation of the Fair k-Center Problem](https://mlsanity.com/paper/2602.16688/) (2026)
- [Multi-View Fair Clustering Guided by Cross-View Sensitive Information Discrepancy](https://mlsanity.com/paper/2609.25811/) (2026)

## Abstract (arXiv)

We introduce a novel problem for diversity-aware clustering. We assume that the potential cluster centers belong to a set of groups defined by protected attributes, such as ethnicity, gender, etc. We then ask to find a minimum-cost clustering of the data into k clusters so that a specified minimum number of cluster centers are chosen from each group. We thus require that all groups are represented in the clustering solution as cluster centers, according to specified requirements. More precisely, we are given a set of clients C, a set of facilities pazocalF, a collection F=F1,dots,Ft of facility groups Fi subseteq pazocalF, budget k, and a set of lower-bound thresholds R=r1,dots,rt, one for each group in F. The diversity-aware k-median problem asks to find a set S of k facilities in pazocalF such that |S cap Fi| ≥ ri, that is, at least ri centers in S are from group Fi, and the k-median cost sumc ∈ C mins ∈ S d(c,s) is minimized. We show that in the general case where the facility groups may overlap, the diversity-aware k-median problem is np-hard, fixed-parameter intractable, and inapproximable to any multiplicative factor. On the other hand, when the facility groups are disjoint, approximation algorithms can be obtained by reduction to the matroid median and red-blue median problems. Experimentally, we evaluate our approximation methods for the tractable cases, and present a relaxation-based heuristic for the theoretically intractable case, which can provide high-quality and efficient solutions for real-world datasets.