Constant Approximation for Individual Preference Stable Clustering

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 \alpha -IP stable if the average distance of every data point to its own cluster is at most \alpha 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.