Volume 17, No 2, 2010, P. 3945
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 sumofsquares clustering (MSSC) of a set of euclidian vectors is proved to be NPcomplete 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, NPcompleteness.
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
