Geodesic
On the complexity of some vector sequence clustering problems
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 2, pp. 47-57

Voir la notice de l'article provenant de la source Math-Net.Ru

It is proved that two problems of clusterization (partition) of a finite Euclidean vectors sequence are NP-complete. In the optimization versions of these problems the aim is to partition the elements of the sequence into a fixed number of clusters minimizing the sum of the squares of the distances from the clusters' elements to their centers. In one of the problems the cardinalities of the clusters are the part of input while in the other problem they are not (they are the optimization variables). Except the center of one-special-cluster, centers of all other clusters are defined as the mean values of all vectors in the cluster. The center of the special cluster is given in advance and is equal to 0. Moreover, the partition must satisfy the restriction that for all vectors that are not in the special cluster the difference between the indices of two consequent vectors from any of these clusters is bounded from below and above by some constants. Bibliogr. 20.
Keywords: clusterization, Euclidean vectors sequence, MSSC, restriction on indices, algorithmic complexity. 
@article{DA_2013_20_2_a3,
     author = {A. V. Kel'manov and A. V. Pyatkin},
     title = {On the complexity of some vector sequence clustering problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {47--57},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_2_a3/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - A. V. Pyatkin
TI  - On the complexity of some vector sequence clustering problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 47
EP  - 57
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_2_a3/
LA  - ru
ID  - DA_2013_20_2_a3
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A A. V. Pyatkin
%T On the complexity of some vector sequence clustering problems
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 47-57
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_2_a3/
%G ru
%F DA_2013_20_2_a3
A. V. Kel'manov; A. V. Pyatkin. On the complexity of some vector sequence clustering problems. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 2, pp. 47-57. http://geodesic.mathdoc.fr/item/DA_2013_20_2_a3/