Theoretical Analysis of the $k$-Means Algorithm - A Survey

Johannes Blömer, Christiane Lammersen, Melanie Schmidt +1

The $k$-means algorithm is one of the most widely used clustering heuristics. Despite its simplicity, analyzing its running time and quality of approximation is surprisingly diffic…