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 α-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.