# Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 33 references that are in the map.
- First posted on arXiv 17 Apr 2026.

## Builds on (most cited first, 15 of 15)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [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)
- [KFC: A Scalable Approximation Algorithm for k-center Fair Clustering](https://mlsanity.com/paper/2010.13949/) (2020)
- [Matroid and Knapsack Center Problems](https://mlsanity.com/paper/1301.0745/) (2013)
- [Fair Colorful k-Center Clustering](https://mlsanity.com/paper/2007.04059/) (2020)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications](https://mlsanity.com/paper/1310.7834/) (2013)
- [Structural Iterative Rounding for Generalized k-Median Problems](https://mlsanity.com/paper/2009.00808/) (2020)
- [Fair Range k-center](https://mlsanity.com/paper/2207.11337/) (2022)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Improved Streaming Algorithm for Fair k-Center Clustering](https://mlsanity.com/paper/2510.05937/) (2025)

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

- [A Sub-4 Approximation for Fair k-Means](https://mlsanity.com/paper/2609.07974/) (2026)

## Abstract (arXiv)

We study discrete k-clustering problems in general metric spaces that are constrained by a combination of two different fairness conditions within the demographic fairness model. Given a metric space (P,d), where every point in P is equipped with a protected attribute, and a number k, the goal is to partition P into k clusters with a designated center each, such that a center-based objective function is minimized and the attributes are fairly distributed with respect to the following two fairness concepts: 1) group fairness: We aim for clusters with balanced numbers of attributes by specifying lower and upper bounds for the desired attribute proportions. 2) diverse center selection: Clusters have natural representatives, i.e., their centers. We ask for a balanced set of representatives by specifying the desired number of centers to choose from each attribute. Dickerson, Esmaeili, Morgenstern and Zhang (2023) denote the combination of these two constraints as doubly constrained fair clustering. They present algorithms whose guarantees depend on the best known approximation factors for either of these problems. Currently, this implies an 8-approximation with a small additive violation on the group fairness constraint. For k-center, we improve this approximation factor to 4 with a small additive violation. This guarantee also depends on the currently best algorithm for DS-fair k-center given by Jones, Nguyen and Nguyen (2020). For k-median and k-means, we propose the first constant-factor approximation algorithms. Our algorithms transform a solution that satisfies diverse center selection into a doubly constrained fair clustering using an LP-based approach. Furthermore, our results are generalizable to other center-selection constraints, such as matroid k-clustering and knapsack constraints.