Geodesic
A $2$-approximation polynomial algorithm for one clustering problem
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 4, pp. 36-45.

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

A $2$-approximation algorithm is presented for one NP-hard data analysis problem. Namely, the problem is to partition a set of Euclidean vectors into two subsets (clusters) under the criterion of minimum sum-of-squares of distances from the elements of clusters to their centers. The center of the first cluster is the average value of vectors in the cluster and the center of the second one is 0. Bibliogr. 16.
Keywords: cluster analysis, search for a vector subset, computational complexity
Mots-clés : approximation polynomial algorithm. 
@article{DA_2013_20_4_a3,
     author = {A. V. Kelmanov and V. I. Khandeev},
     title = {A $2$-approximation polynomial algorithm for one clustering problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {36--45},
     publisher = {mathdoc},
     volume = {20},
     number = {4},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_4_a3/}
}
TY  - JOUR
AU  - A. V. Kelmanov
AU  - V. I. Khandeev
TI  - A $2$-approximation polynomial algorithm for one clustering problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 36
EP  - 45
VL  - 20
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_4_a3/
LA  - ru
ID  - DA_2013_20_4_a3
ER  - 
%0 Journal Article
%A A. V. Kelmanov
%A V. I. Khandeev
%T A $2$-approximation polynomial algorithm for one clustering problem
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 36-45
%V 20
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_4_a3/
%G ru
%F DA_2013_20_4_a3
A. V. Kelmanov; V. I. Khandeev. A $2$-approximation polynomial algorithm for one clustering problem. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 4, pp. 36-45. http://geodesic.mathdoc.fr/item/DA_2013_20_4_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] Gimadi E. Kh., Pyatkin A. V., Rykov I. A., “O polinomialnoi razreshimosti nekotorykh zadach vybora podmnozhestva vektorov v evklidovom prostranstve fiksirovannoi razmernosti”, Diskret. analiz i issled. operatsii, 15:6 (2008), 11–19 | MR | Zbl

[3] Dolgushev A. V., Kelmanov A. V., “Priblizhënnyi algoritm resheniya odnoi zadachi klasternogo analiza”, Diskret. analiz i issled. operatsii, 18:2 (2011), 29–40 | MR | Zbl

[4] 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

[5] 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

[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] 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.

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

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

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

[12] 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

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

[14] MacQueen J. B., “Some methods for classification and analysis of multivariate observations”, Proc. 5th Berkeley Symp. Math. Stat. Probab., v. 1, 1967, 281–297 | MR | Zbl

[15] Mahajan M., Nimbhorkar P., Varadarajan K., “The planar $k$-means problem is NP-hard”, Lect. Notes Comput. Sci., 5431, 2009, 284–285 | MR

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