Volume 20, No 4, 2013, P. 3645
UDC 519.2+621.391
Kel’manov A. V., Khandeev V. I.
A 2approximation polynomial algorithm for one clustering problem
Abstract:
A 2approximation algorithm is presented for one NPhard data analysis problem. Namely, the problem is to partition a set of Euclidean vectors into two subsets (clusters) under the criterion of minimum sumofsquares 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 0.
Bibliogr. 16.
Keywords: cluster analysis, search for a vector subset, computational complexity, approximation polynomial algorithm.
Kelmanov Alexander Vasilyevich ^{1,2}
Khandeev Vladimir Il’ich ^{2}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
email: kelm@math.nsc.ru, vladimir.handeev@gmail.com
