# Approximating Fair Clustering with Cascaded Norm Objectives

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 38 references that are in the map.
- First posted on arXiv 8 Nov 2021.

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

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (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)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [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)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (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)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [A Notion of Individual Fairness for Clustering](https://mlsanity.com/paper/2006.04960/) (2020)
- [Approximation Algorithms for Minimum Norm and Ordered Optimization Problems](https://mlsanity.com/paper/1811.05022/) (2018)
- [The Densest k-Subhypergraph Problem](https://mlsanity.com/paper/1605.04284/) (2016)
- [Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion](https://mlsanity.com/paper/1611.07866/) (2016)
- [New Approximability Results for the Robust k-Median Problem](https://mlsanity.com/paper/1309.4602/) (2013)
- [On Uniform Capacitated k-Median Beyond the Natural LP Relaxation](https://mlsanity.com/paper/1409.6739/) (2014)
- [Generalized Center Problems with Outliers](https://mlsanity.com/paper/1805.02217/) (2018)
- [Sherali-Adams Integrality Gaps Matching the Log-Density Threshold](https://mlsanity.com/paper/1804.07842/) (2018)
- [LP-Based Algorithms for Capacitated Facility Location](https://mlsanity.com/paper/1407.3263/) (2014)

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

- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [Fair Representation Clustering with Several Protected Classes](https://mlsanity.com/paper/2202.01391/) (2022)
- [Spectral Normalized-Cut Graph Partitioning with Fairness Constraints](https://mlsanity.com/paper/2307.12065/) (2023)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [Measuring and mitigating voting access disparities: a study of race and polling locations in Florida and North Carolina](https://mlsanity.com/paper/2205.14867/) (2022)
- [Socially Fair Center-based and Linear Subspace Clustering](https://mlsanity.com/paper/2208.10095/) (2022)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)
- [Clustering to Minimize Cluster-Aware Norm Objectives](https://mlsanity.com/paper/2410.24104/) (2024)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [A Broader View on Clustering under Cluster-Aware Norm Objectives](https://mlsanity.com/paper/2512.06211/) (2025)

## Abstract (arXiv)

We introduce the (p,q)-Fair Clustering problem. In this problem, we are given a set of points P and a collection of different weight functions W. We would like to find a clustering which minimizes the ℓq-norm of the vector over W of the ℓp-norms of the weighted distances of points in P from the centers. This generalizes various clustering problems, including Socially Fair k-Median and k-Means, and is closely connected to other problems such as Densest k-Subgraph and Min k-Union. We utilize convex programming techniques to approximate the (p,q)-Fair Clustering problem for different values of p and q. When p≥ q, we get an O(k(p-q)/(2pq)), which nearly matches a kOmega((p-q)/(pq)) lower bound based on conjectured hardness of Min k-Union and other problems. When q≥ p, we get an approximation which is independent of the size of the input for bounded p,q, and also matches the recent O((log n/(loglog n))1/p)-approximation for (p, ∞)-Fair Clustering by Makarychev and Vakilian (COLT 2021).