Exact Euclidean k-Means: Faster in the Plane, Hard Beyond ItResearch Paper
Exact Euclidean k-means asks for the least possible sum of squared distances from data points to freely located centers. Two parameters shape the problem: the number of centers, k, and the ambient dimension, d. An algorithm whose exponent depends on their product can be polynomial for every fixed pair and still become impractical as either parameter grows.…