Brief Announcement: Streaming Balanced Clustering
Hossein Esfandiari, Vahab Mirrokni, Peilin Zhong · 2023
Clustering of data points in metric space is among the most fundamental problems in computer science with plenty of applications in data mining, information retrieval and machine learning. Many of these applications deal with large datasets, and hence researchers focused on designing algorithms for these problems in large scale settings such as the streaming setting. One of the sweet versions of clustering problems is balanced clustering (or more generally capacitated clustering), where we do not desire to have some giant and several small clusters. Despite the importance of the context, the best known streaming algorithm for capacitated clustering is far from optimal. The state-of-the-art streaming algorithm for capacitated clustering gives an O(1)-approximate solution, requires three passes and only handles insertions (Bateni et al. NeurIPS'14).