Geodesic
On the complexity of some cluster analysis problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 51 (2011) no. 11, pp. 2106-2112 
A. V. Kel'manov. On the complexity of some cluster analysis problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 51 (2011) no. 11, pp. 2106-2112. http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_11_a13/
@article{ZVMMF_2011_51_11_a13,
     author = {A. V. Kel'manov},
     title = {On the complexity of some cluster analysis problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {2106--2112},
     year = {2011},
     volume = {51},
     number = {11},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_11_a13/}
}
TY  - JOUR
AU  - A. V. Kel'manov
TI  - On the complexity of some cluster analysis problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2011
SP  - 2106
EP  - 2112
VL  - 51
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_11_a13/
LA  - ru
ID  - ZVMMF_2011_51_11_a13
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%T On the complexity of some cluster analysis problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2011
%P 2106-2112
%V 51
%N 11
%U http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_11_a13/
%G ru
%F ZVMMF_2011_51_11_a13

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

NP-completeness of certain important clusterization problems for a finite set of vectors is proved.

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

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

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

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

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

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

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

[8] Kelmanov A. V., Pyatkin A. V., “Ob odnom variante zadachi vybora podmnozhestva vektorov”, Diskretnyi analiz i issl. operatsii, 15:5 (2008), 25–40 | MR

[9] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach poiska podmnozhestv vektorov i klasternogo analiza”, Zh. vychisl. matem. i matem. fiz., 49:11 (2009), 2059–2067 | MR

[10] Kelmanov A. V., Pyatkin A. V., “NP-polnota nekotorykh zadach vybora podmnozhestva vektorov”, Diskretnyi analiz i issl. operatsii, 17:5 (2010), 37–45 | MR

[11] Kelmanov A. V., “O slozhnosti nekotorykh zadach analiza dannykh”, Zh. vychisl. matem. i matem. fiz., 50:11 (2010), 2045–2051 | MR

[12] Kelmanov A. V., “NP-polnota nekotorykh zadach poiska podmnozhestv vektorov”, Tr. In-ta matem. i mekhan. UrO RAN. Ekaterinburg, 16:3 (2010), 121–129

[13] Kelmanov A. V., “NP-polnota nekotorykh zadach analiza dannykh”, Intellektualizatsiya obrabotki informatsii: 8-ya mezhdunar. konf., Sb. dokl. (Resp. Kipr, g. Pafos, 17–24 oktyabrya 2010 g.), MAKS Press, M., 2010, 262–265