Volume 18, No 2, 2011, P. 2940
UDC 519.2+621.391
A. V. Dolgushev, A. V. Kel’manov
An approximation algorithm for one problem of cluster analysis
Abstract:
A 2approximation algorithm is presented for a data analysis problem which was previously reduced to an NPhard optimization problem. Particularly, the problem is to partition a set of Euclidean vectors into two subsets (clusters) under the criterion of minimumsumofsquares.
Bibliogr. 7.
Keywords: search for a vector subset, cluster analysis, NPhardness, 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
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
email: dolgushev@math.nsc.ru, kelm@math.nsc.ru
