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/

[1] Gimadi E. Kh., Kelmanov A. V., Kelmanova M. A., Khamidullin S. A., “Aposteriornoe obnaruzhenie v chislovoi posledovatelnosti kvaziperiodicheskogo fragmenta pri zadannom chisle povtorov”, Sib. zhurn. industr. matematiki, 9:1 (2006), 55–74 | MR | Zbl

[2] Dolgushev A. V., Kelmanov A. V., “K voprosu ob algoritmicheskoi slozhnosti odnoi zadachi klasternogo analiza”, Diskret. analiz i issled. operatsii, 17:2 (2010), 39–45 | MR | Zbl

[3] Kelmanov A. V., “Problema off-line obnaruzheniya povtoryayuschegosya fragmenta v chislovoi posledovatelnosti”, Tr. In-ta matematiki i mekhaniki UrO RAN, 14, no. 2, 2008, 81–88 | Zbl

[4] Kelmanov A. V., Mikhailova L. V., “Sovmestnoe obnaruzhenie v kvaziperiodicheskoi posledovatelnosti zadannogo chisla fragmentov iz etalonnogo nabora i ee razbienie na uchastki, vklyuchayuschie serii odinakovykh fragmentov”, Zhurn. vychisl. matematiki i mat. fiziki, 46:1 (2006), 172–189 | MR | Zbl

[5] Kelmanov A. V., Mikhailova L. V. Khamidullin S. A., “Ob odnoi zadache poiska uporyadochennykh naborov fragmentov v chislovoi posledovatelnosti”, Diskret. analiz i issled. operatsii, 16:4 (2009), 31–46 | MR

[6] Kelmanov A. V., Pyatkin A. V., “O slozhnosti odnogo iz variantov zadachi vybora podmnozhestva “pokhozhikh” vektorov”, Dokl. RAN, 421:5 (2008), 590–592 | MR

[7] Kelmanov A. V., Pyatkin A. V., “Ob odnom variante zadachi vybora podmnozhestva vektorov”, Diskret. analiz i issled. operatsii, 15:5 (2008), 20–34 | MR

[8] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach poiska podmnozhestv vektorov i klasternogo analiza”, Zhurn. vychisl. matematiki i mat. fiziki, 49:11 (2009), 2059–2067 | MR

[9] Kelmanov A. V., Khamidullin S. A., “Aposteriornoe obnaruzhenie zadannogo chisla odinakovykh podposledovatelnostei v kvaziperiodicheskoi posledovatelnosti”, Zhurn. vychisl. matematiki i mat. fiziki, 41:5 (2001), 807–820 | MR | Zbl

[10] Aloise D., Deshpande A., Hansen P., Popat P., NP-hardness of Euclidean sum-of-squares clustering, Les Cahiers du GERAD, G-2008-33, 2008, 4 pp.

[11] Aloise D., Hansen P., On the complexity of minimum sum-of-squares clustering, Les Cahiers du GERAD, G-2007-50, 2007, 12 pp.

[12] Anil K., Jain K., “Data clustering: 50 years beyond $k$-means”, Pattern Recognit. Lett., 31 (2010), 651–666

[13] Edwards A. W. F., Cavalli-Sforza L. L., “A method for cluster analysis”, Biometrics, 21 (1965), 362–375

[14] Garey M. R., Johnson D. S., Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979, 314 pp. | MR | Zbl

[15] Inaba M., Katch N., Imai H., “Applications of weighted Voronoi diagrams and randomization to variance-based clustering”, Proc. 10th Ann. Symp. Comput. Geom. (Stony Brook, New York, June 06–08, 1994), ACM Press, Stony Brook, New York, NY, 1994, 332–339

[16] Kel'manov A. V., Jeon B., “A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train”, IEEE Trans. Signal Processing, 52:3 (2004), 645–656 | MR

[17] Kel'manov A. V., Khamidullin S. A., “An algorithm for recognition of a vector alphabet generating a sequence with a quasi-periodic structure”, Pattern Recognition Image Anal., 20:4 (2010), 451–458

[18] Mahajan M., Nimbhorkar P., Varadarajan K., “The planar $k$-means problem is NP-hard”, Theor. Comput. Sci., 442 (2012), 13–21 | MR | Zbl

[19] MacQueen J. B., “Some methods for classification and analysis of multivariate observations”, Proc. 5th Berkeley Symp. Math. Statist. Probab. (California, Berkeley, June 21 – July 18, 1965; December 27, 1965 – January 7, 1966), v. 1, University of California Press, Berkeley, California, 1967, 281–297 | MR | Zbl

[20] Rao M., “Cluster analysis and mathematical programming”, J. Amer. Stat. Assoc., 66 (1971), 622–626 | Zbl