Volume 18, No 2, 2011, P. 29-40

UDC 519.2+621.391
A. V. Dolgushev, A. V. Kel’manov
An approximation algorithm for one problem of cluster analysis

Abstract:
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.
Bibliogr. 7.

Keywords: search for a vector subset, cluster analysis, NP-hardness, efficient approximate algorithm.

Dolgushev Aleksey Vladimirovich ²
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
e-mail: dolgushev@math.nsc.ru, kelm@math.nsc.ru