On the complexity of some vector sequence clustering problems

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.