# Diversity-aware clustering: Computational Complexity and Approximation Algorithms

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 70 references that are in the map.
- First posted on arXiv 10 Jan 2024.

## Builds on (most cited first, 30 of 31)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [An Empirical Study of Rich Subgroup Fairness for Machine Learning](https://mlsanity.com/paper/1808.08166/) (2018)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Fairness Through Computationally-Bounded Awareness](https://mlsanity.com/paper/1803.03239/) (2018)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [Characterizing Intersectional Group Fairness with Worst-Case Comparisons](https://mlsanity.com/paper/2101.01673/) (2021)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [Diversity-aware k-median : Clustering with fair center representation](https://mlsanity.com/paper/2106.11696/) (2021)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Matroid and Knapsack Center Problems](https://mlsanity.com/paper/1301.0745/) (2013)
- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [An Improved Local Search Algorithm for k-Median](https://mlsanity.com/paper/2111.04589/) (2021)
- [Tight FPT Approximations for k-Median and k-Means](https://mlsanity.com/paper/1904.12334/) (2019)
- [A Constant Approximation for Colorful k-Center](https://mlsanity.com/paper/1907.08906/) (2019)
- [Clustering with fair-center representation: parameterized approximation algorithms and heuristics](https://mlsanity.com/paper/2112.07030/) (2021)
- [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)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [Tight FPT Approximation for Constrained k-Center and k-Supplier](https://mlsanity.com/paper/2110.14242/) (2021)
- [Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces](https://mlsanity.com/paper/2305.07316/) (2023)
- [Approximating capacitated k-median with (1+ε)k open facilities](https://mlsanity.com/paper/1411.5630/) (2014)

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

- [Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights](https://mlsanity.com/paper/2410.12913/) (2024)
- [Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means](https://mlsanity.com/paper/2604.16061/) (2026)
- [On the Hardness of Approximation of the Fair k-Center Problem](https://mlsanity.com/paper/2602.16688/) (2026)

## Abstract (arXiv)

In this work, we study diversity-aware clustering problems where the data points are associated with multiple attributes resulting in intersecting groups. A clustering solution needs to ensure that the number of chosen cluster centers from each group should be within the range defined by a lower and upper bound threshold for each group, while simultaneously minimizing the clustering objective, which can be either k-median, k-means or k-supplier. We study the computational complexity of the proposed problems, offering insights into their NP-hardness, polynomial-time inapproximability, and fixed-parameter intractability. We present parameterized approximation algorithms with approximation ratios 1+ frac2e + ε ≈ 1.736, 1+frac8e + ε ≈ 3.943, and 5 for diversity-aware k-median, diversity-aware k-means and diversity-aware k-supplier, respectively. Assuming Gap-ETH, the approximation ratios are tight for the diversity-aware k-median and diversity-aware k-means problems. Our results imply the same approximation factors for their respective fair variants with disjoint groups -- fair k-median, fair k-means, and fair k-supplier -- with lower bound requirements.