Scalable Algorithms for Individual Preference Stable Clustering
This addresses fairness and stability in clustering for data points, but it is incremental as it refines an existing local search approach.
The paper tackles the problem of achieving individual preference stable clustering, which ensures fairness and stability by bounding each point's average distance to its cluster relative to others, and shows that a local search algorithm guarantees O(log n)-IP stability and runs in almost linear time.
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(\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)$.