Spotlight Poster

Constant Approximation for Individual Preference Stable Clustering

Anders Aamand · Justin Chen · Allen Liu · Sandeep Silwal · Pattara Sukprasert · Ali Vakilian · Fred Zhang

Great Hall & Hall B1+B2 (level 1) #1013
[ ]
Tue 12 Dec 3:15 p.m. PST — 5:15 p.m. PST

Abstract: 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. 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.

Chat is not available.