Volume 17, No 2, 2010, P. 39-45

UDC 519.2+621.391
A. V. Dolgushev and A. V. Kel’manov
On the issue of algorithmic complexity of one cluster analysis problem

Abstract:
In the paper the problem of minimum sum-of-squares clustering (MSSC) of a set of euclidian vectors is proved to be NP-complete when the dimension of the space is a part and the number of clusters is not a part of the input.
Bibl. 9.

Keywords: clustering, MSSC, algorithmic complexity, NP-completeness.

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