Constant Approximation for Individual Preference Stable Clustering
Anders Aamand Justin Y. Chen Allen Liu Sandeep Silwal Pattara Sukprasert Ali Vakilian Fred Zhang
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 \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.