# Clustering with fair-center representation: parameterized approximation algorithms and heuristics

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2021.

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

- [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)
- [Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights](https://mlsanity.com/paper/2410.12913/) (2024)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [Unbiased Binning for Fairness-aware Attribute Representation](https://mlsanity.com/paper/2509.21785/) (2025)
- [On the Hardness of Approximation of the Fair k-Center Problem](https://mlsanity.com/paper/2602.16688/) (2026)

## Abstract (arXiv)

We study a variant of classical clustering formulations in the context of algorithmic fairness, known as diversity-aware clustering. In this variant we are given a collection of facility subsets, and a solution must contain at least a specified number of facilities from each subset while simultaneously minimizing the clustering objective (k-median or k-means). We investigate the fixed-parameter tractability of these problems and show several negative hardness and inapproximability results, even when we afford exponential running time with respect to some parameters. Motivated by these results we identify natural parameters of the problem, and present fixed-parameter approximation algorithms with approximation ratios big(1 + frac2e +ε big) and big(1 + frac8e+ ε big) for diversity-aware k-median and diversity-aware k-means respectively, and argue that these ratios are essentially tight assuming the gap-exponential time hypothesis. We also present a simple and more practical bicriteria approximation algorithm with better running time bounds. We finally propose efficient and practical heuristics. We evaluate the scalability and effectiveness of our methods in a wide variety of rigorously conducted experiments, on both real and synthetic data.