# Fair Polylog-Approximate Low-Cost Hierarchical Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 24 references that are in the map.
- First posted on arXiv 21 Nov 2023.

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

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Discrimination in Online Ad Delivery](https://mlsanity.com/paper/1301.6822/) (2013)
- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [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)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [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)
- [Protecting the Protected Group: Circumventing Harmful Fairness](https://mlsanity.com/paper/1905.10546/) (2019)
- [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, 2 of 2)

- [Robust Fair Clustering with Group Membership Uncertainty Sets](https://mlsanity.com/paper/2406.00599/) (2024)
- [Welfare-Centric Clustering](https://mlsanity.com/paper/2508.10345/) (2025)

## Abstract (arXiv)

Research in fair machine learning, and particularly clustering, has been crucial in recent years given the many ethical controversies that modern intelligent systems have posed. Ahmadian et al. [2020] established the study of fairness in textithierarchical clustering, a stronger, more structured variant of its well-known flat counterpart, though their proposed algorithm that optimizes for Dasgupta's [2016] famous cost function was highly theoretical. Knittel et al. [2023] then proposed the first practical fair approximation for cost, however they were unable to break the polynomial-approximate barrier they posed as a hurdle of interest. We break this barrier, proposing the first truly polylogarithmic-approximate low-cost fair hierarchical clustering, thus greatly bridging the gap between the best fair and vanilla hierarchical clustering approximations.