Volume 20, No 4, 2013, P. 36-45

UDC 519.2+621.391
Kel’manov A. V., Khandeev V. I.
A 2-approximation polynomial algorithm for one clustering problem

Abstract:
A 2-approximation algorithm is presented for one NP-hard data analysis problem. Namely, the problem is to partition 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 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 ²
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
e-mail: kelm@math.nsc.ru, vladimir.handeev@gmail.com