# Doubly Constrained Fair Clustering arXiv: https://arxiv.org/abs/2305.19475 · HTML: https://mlsanity.com/paper/2305.19475/ ## Key facts - Cited by 9 papers in the map (data through 14 Oct 2026). - Builds on 31 of its 43 references that are in the map. - First posted on arXiv 31 May 2023. ## Builds on (most cited first, 30 of 31) - [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014) - [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016) - [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016) - [Fairness in Criminal Justice Risk Assessments: The State of the Art](https://mlsanity.com/paper/1703.09207/) (2017) - [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018) - [Mitigating Bias in Algorithmic Hiring: Evaluating Claims and Practices](https://mlsanity.com/paper/1906.09208/) (2019) - [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019) - [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019) - [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019) - [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019) - [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020) - [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019) - [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018) - [Fairness Under Composition](https://mlsanity.com/paper/1806.06122/) (2018) - [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020) - [Probabilistic Fair Clustering](https://mlsanity.com/paper/2006.10916/) (2020) - [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020) - [A Center in Your Neighborhood: Fairness in Facility Location](https://mlsanity.com/paper/1908.09041/) (2019) - [A Pairwise Fair and Community-preserving Approach to k-Center Clustering](https://mlsanity.com/paper/2007.07384/) (2020) - [Fair Hierarchical Clustering](https://mlsanity.com/paper/2006.10221/) (2020) - [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021) - [A Notion of Individual Fairness for Clustering](https://mlsanity.com/paper/2006.04960/) (2020) - [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021) - [Diversity-aware k-median : Clustering with fair center representation](https://mlsanity.com/paper/2106.11696/) (2021) - [Scalable Spectral Clustering with Group Fairness Constraints](https://mlsanity.com/paper/2210.16435/) (2022) - [Fair Algorithms for Hierarchical Agglomerative Clustering](https://mlsanity.com/paper/2005.03197/) (2020) - [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021) - [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022) - [Improved Approximation for Fair Correlation Clustering](https://mlsanity.com/paper/2206.05050/) (2022) - [Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost](https://mlsanity.com/paper/2205.14198/) (2022) ## Built on by (most cited first, 9 of 9) - [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023) - [Robust Fair Clustering with Group Membership Uncertainty Sets](https://mlsanity.com/paper/2406.00599/) (2024) - [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024) - [The Fairness-Quality Trade-off in Clustering](https://mlsanity.com/paper/2408.10002/) (2024) - [A Computational Approach to Improving Fairness in K-means Clustering](https://mlsanity.com/paper/2505.22984/) (2025) - [Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means](https://mlsanity.com/paper/2604.16061/) (2026) - [Efficient k-means with Individual Fairness via Exponential Tilting](https://mlsanity.com/paper/2406.16557/) (2024) - [Welfare-Centric Clustering](https://mlsanity.com/paper/2508.10345/) (2025) - [SubQuad: Near-Quadratic-Free Structure Inference with Distribution-Balanced Objectives in Adaptive Receptor framework](https://mlsanity.com/paper/2602.17330/) (2026) ## Abstract (arXiv) The remarkable attention which fair clustering has received in the last few years has resulted in a significant number of different notions of fairness. Despite the fact that these notions are well-justified, they are often motivated and studied in a disjoint manner where one fairness desideratum is considered exclusively in isolation from the others. This leaves the understanding of the relations between different fairness notions as an important open problem in fair clustering. In this paper, we take the first step in this direction. Specifically, we consider the two most prominent demographic representation fairness notions in clustering: (1) Group Fairness (GF), where the different demographic groups are supposed to have close to population-level representation in each cluster and (2) Diversity in Center Selection (DS), where the selected centers are supposed to have close to population-level representation of each group. We show that given a constant approximation algorithm for one constraint (GF or DS only) we can obtain a constant approximation solution that satisfies both constraints simultaneously. Interestingly, we prove that any given solution that satisfies the GF constraint can always be post-processed at a bounded degradation to the clustering cost to additionally satisfy the DS constraint while the reverse is not true. Furthermore, we show that both GF and DS are incompatible (having an empty feasibility set in the worst case) with a collection of other distance-based fairness notions. Finally, we carry experiments to validate our theoretical findings.