1. The Problem One of the most popular algorithms for clustering is k-means. We start with data vectors . We choose vectors — cluster centers — to minimize the error Unfortunately, finding to minimize is NP-hard. The usual iterative method, hrefnosnap{http://en.wikipedia.org/wiki/Lloyd is easy to implement but it is unlikely to come close to minimizing the [...]