Monte Carlo approximation certificates for k-means clustering

Dustin G. Mixon, Soledad Villar

Efficient algorithms for $k$-means clustering frequently converge to suboptimal partitions, and given a partition, it is difficult to detect $k$-means optimality. In this paper, we…