Scalable Algorithms for Individual Preference Stable Clustering
Ron Mosenzon Ali Vakilian
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 $\alpha$-IP stable when each data point's average
distance to its cluster is no more than $\alpha$ 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(\log n)$-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, $\tilde{O}(nk)$.