A. V. Dolgushev, A. V. Kel'manov, “On the issue of algorithmic complexity of one cluster analysis problem”, Diskretn. Anal. Issled. Oper., 2010, Volume 17, Issue 2,Pages <nobr>39

This article is cited in 12 papers

On the issue of algorithmic complexity of one cluster analysis problem

A. V. Dolgushev^a, A. V. Kel'manov^ba

^a Novosibirsk State University, Novosibirsk, Russia
^b S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia

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.

UDC: 519.2+621.391

Received: 01.12.2009
Revised: 17.12.2009