Geodesic
Complexity of certain problems of searching for subsets of vectors and cluster analysis
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 11, pp. 2059-2065 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The discrete extremal problems to which certain problems of searching for subsets of vectors and cluster analysis are reduced are proved to be NP-complete. 
@article{ZVMMF_2009_49_11_a11,
     author = {A. V. Kel'manov and A. V. Pyatkin},
     title = {Complexity of certain problems of searching for subsets of vectors and cluster analysis},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {2059--2065},
     year = {2009},
     volume = {49},
     number = {11},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_11_a11/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - A. V. Pyatkin
TI  - Complexity of certain problems of searching for subsets of vectors and cluster analysis
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2009
SP  - 2059
EP  - 2065
VL  - 49
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_11_a11/
LA  - ru
ID  - ZVMMF_2009_49_11_a11
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A A. V. Pyatkin
%T Complexity of certain problems of searching for subsets of vectors and cluster analysis
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2009
%P 2059-2065
%V 49
%N 11
%U http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_11_a11/
%G ru
%F ZVMMF_2009_49_11_a11
A. V. Kel'manov; A. V. Pyatkin. Complexity of certain problems of searching for subsets of vectors and cluster analysis. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 11, pp. 2059-2065. http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_11_a11/

[1] Kelmanov A. B., Khamidullin S. A., “Aposteriornoe obnaruzhenie zadannogo chisla odinakovykh podposledovatelnostei v kvaziperiodicheskoi posledovatelnosti”, Zh. vychisl. matem. i matem. fiz., 41:5 (2001), 807–820 | MR

[2] Kel'manov A. V., Jeon B., “A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train”, IEEE Transactions on Signal Processing, 52:3 (2004), 1–12 | DOI | MR

[3] Kelmanov A. B., Mikhailova L. V., “Sovmestnoe obnaruzhenie v kvaziperiodicheskoi posledovatelnosti zadannogo chisla fragmentov iz etalonnogo nabora i ee razbienie na uchastki, vklyuchayuschie serii odinakovykh fragmentov”, Zh. vychisl. matem. i matem. fiz., 46:1 (2006), 172–189 | MR

[4] Kelmanov A. B., Mikhailova L. V., “Aposteriornoe obnaruzhenie kvaziperiodicheskikh fragmentov iz etalonnogo nabora v chislovoi posledovatelnosti”, Zh. vychisl. matem. i matem. fiz., 48:5 (2008), 899–915 | MR

[5] Kelmanov A. B., Mikhailova L. V., Khamidullin S. A., “Aposteriornoe obnaruzhenie v kvaziperiodicheskoi posledovatelnosti povtoryayuschegosya nabora etalonnykh fragmentov”, Zh. vychisl. matem. i matem. fiz., 48:12 (2008), 2247–2260 | MR

[6] Kelmanov A. B., “Polinomialno razreshimye i NP-trudnye varianty zadachi optimalnogo obnaruzheniya v chislovoi posledovatelnosti povtoryayuschegosya fragmenta”, Materialy Ros. konf. “Diskretnaya optimizatsiya i issledovanie operatsii” (Vladivostok, 7–14 sentyabrya 2007), IM SO RAN, Novosibirsk, 2007, 46–50; http://math.nsc.ru/conference/door07/DOOR-abstracts.pdf

[7] Kelmanov A. V., “Problema off-line obnaruzheniya povtoryayuschegosya fragmenta v chislovoi posledovatelnosti”, Tr. IMM URO RAN. Ekaterinburg, 14, no. 2, 2008, 81–88 | MR

[8] Gimadi E. Kh., Kelmanov A. B., Kelmanova M. A., Khamidullin S. A., “Aposteriornoe obnaruzhenie v chislovoi posledovatelnosti kvaziperiodicheskogo fragmenta pri zadannom chisle povtorov”, Sibirskii zhurnal industr. matem., 9:1(25) (2006), 55–74 | MR

[9] Baburin A. E., Gimadi E. Kh., Glebov H. H., Pyatkin A. B., “Zadacha otyskaniya podmnozhestva vektorov s maksimalnym summarnym vesom”, Diskretnyi analiz i issl. operatsii. Ser. 2, 14:1 (2007), 32–42 | MR

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

[11] Kelmanov A. B., Pyatkin A. B., “Ob odnom variante zadachi vybora podmnozhestva vektorov”, Diskretnyi analiz i issl. operatsii, 15:5 (2008), 20–34 | MR

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

[13] Drineas P., Frieze A., Kannan R., Vinay V., “Clustering large graphs via the singular value decomposition”, Machine Learning, 56 (2004), 9–33 | DOI | Zbl

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

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

[16] http://math.nsc.ru/~serge/qpsl/