A 2-approximation polynomial algorithm for a clustering problem
Alexander V. Kel’manov, ВЛАДИМИР ИЛЬИЧ ХАНДЕЕВ · Journal of Applied and Industrial Mathematics · 2013
A 2-approximation algorithm is presented for some NP-hard data analysis problem that consists in partitioning a set of Euclidean vectors into two subsets (clusters) under the criterion of minimum sum-of-squares of distances from the elements of clusters to their centers. The center of the first cluster is the average value of vectors in the cluster, and the center of the second one is the origin.