Further heuristics for $k$-means: The merge-and-split heuristic and the $(k,l)$-means

Frank Nielsen, Richard Nock

Finding the optimal $k$-means clustering is NP-hard in general and many heuristics have been designed for minimizing monotonically the $k$-means objective. We first show how to ext…