[edit]
Scalable Algorithms for Individual Preference Stable Clustering
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:1108-1116, 2024.
Abstract
In this paper, we study the individual preference (IP) stability, which is an notion capturing individual fairness and stability in clustering. Within this setting, a clustering is α-IP stable when each data point’s average distance to its cluster is no more than α times its average distance to any other cluster. In this paper, we study the natural local search algorithm for IP stable clustering. Our analysis confirms a O(logn)-IP stability guarantee for this algorithm, where n denotes the number of points in the input. Furthermore, by refining the local search approach, we show it runs in an almost linear time, ˜O(nk).