Volume 18, No 2, 2011, P. 29-40
A. V. Dolgushev, A. V. Kel’manov
An approximation algorithm for one problem of cluster analysis
A 2-approximation algorithm is presented for a data analysis problem which was previously reduced to an NP-hard optimization problem. Particularly, the problem is to partition a set of Euclidean vectors into two subsets (clusters) under the criterion of minimum-sum-of-squares.
Keywords: search for a vector subset, cluster analysis, NP-hardness, efficient approximate algorithm.
Dolgushev Aleksey Vladimirovich 2
Kel’manov Alexander Vasilyevich 1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: email@example.com, firstname.lastname@example.org