# Constant Approximation for Individual Preference Stable Clustering

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 28 Sep 2023.

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

- [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)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [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)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints](https://mlsanity.com/paper/2103.02013/) (2021)
- [Distributional Individual Fairness in Clustering](https://mlsanity.com/paper/2006.12589/) (2020)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [Feature-based Individual Fairness in k-Clustering](https://mlsanity.com/paper/2109.04554/) (2021)
- [Faster Linear Algebra for Distance Matrices](https://mlsanity.com/paper/2210.15114/) (2022)

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

- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [Metric Hedonic Games on the Line](https://mlsanity.com/paper/2602.05888/) (2026)

## Abstract (arXiv)

Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is α-IP stable if the average distance of every data point to its own cluster is at most α times the average distance to any other cluster. Unfortunately, determining if a dataset admits a 1-IP stable clustering is NP-Hard. Moreover, before this work, it was unknown if an o(n)-IP stable clustering always exists, as the prior state of the art only guaranteed an O(n)-IP stable clustering. We close this gap in understanding and show that an O(1)-IP stable clustering always exists for general metrics, and we give an efficient algorithm which outputs such a clustering. We also introduce generalizations of IP stability beyond average distance and give efficient, near-optimal algorithms in the cases where we consider the maximum and minimum distances within and between clusters.