Constant Approximation for Individual Preference Stable Clustering
It addresses a theoretical gap in clustering stability with fairness implications, providing a constant approximation where prior work only guaranteed linear factors.
The paper tackles the problem of determining whether constant-factor individual preference stable clusterings always exist for general metrics, showing that an O(1)-IP stable clustering always exists and providing an efficient algorithm to compute it, with extensions to generalizations using maximum and minimum distances.
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 \emph{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.