Clustering with Label Consistency
This addresses the need for stable cluster assignments in real-world applications, representing an incremental improvement over traditional methods.
The paper tackles the problem of ensuring stable point labels in metric clustering, introducing a new notion of label consistency and designing consistent approximation algorithms for k-center and k-median problems.
Designing efficient, effective, and consistent metric clustering algorithms is a significant challenge attracting growing attention. Traditional approaches focus on the stability of cluster centers; unfortunately, this neglects the real-world need for stable point labels, i.e., stable assignments of points to named sets (clusters). In this paper, we address this gap by initiating the study of label-consistent metric clustering. We first introduce a new notion of consistency, measuring the label distance between two consecutive solutions. Then, armed with this new definition, we design new consistent approximation algorithms for the classical $k$-center and $k$-median problems.