I have the following problem - i have a range of numbers (ie. [1, 5, 7, 8, 15, 29, 100]). I need to cluster them OPTIMALLY (not local optimum as in lloyd algorithm) and better than NP time, minimizing as in k-means problem (to find points such that squared distances from clustroids to points of clusters are minimized).
So far I found only some paper on the dynamic solution for k-means but it seems too difficult. Can someone suggest some possible way to do this.