The $NP$-completeness of some problems of searching for vector subsets

A. V. Kel'manov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 3, pp. 121-129

Résumé

We prove the $NP$-completeness of discrete optimization problems, to which some important problems appearing in data analysis involving a search for a vector subset are reduced.

Détail

Keywords: extremal problem, complexity, $NP$-completeness, search for subsets, Euclidean space, data analysis.

Bibliographie

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

[2] Dasgupta S., The hardness of $k$-means clustering, Technical Report. CS2007-0890, University of California, San Diego, 2007, 6 pp.

[3] Mahajan M., Nimbhorkar P., Varadarajan K., “The planar $k$-means problem is $NP$-hard”, Lecture Notes Comput. Sci., 5431, 2009, 274–285 | Zbl

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

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

[6] 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(25) (2006), 55–74 | MR

[7] Baburin A. E., Gimadi E. Kh., Glebov N. I., Pyatkin A. V., “Zadacha otyskaniya podmnozhestva vektorov s maksimalnym summarnym vesom”, Diskret. analiz i issled. operatsii. Ser. 2, 14:1 (2007), 32–42 | MR

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

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

[10] 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–2065 | MR

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

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

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

[15] Kelmanov A. V., Mikhailova L. V., Khamidullin S. A., “Aposteriornoe obnaruzhenie v kvaziperiodicheskoi posledovatelnosti povtoryayuschegosya nabora etalonnykh fragmentov”, Zhurn. vychisl. matematiki i mat. fiziki, 48:12 (2008), 2247–2260 | MR

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

[17] Kelmanov A. V., “Polinomialno razreshimye i $NP$-trudnye varianty zadachi optimalnogo obnaruzheniya v chislovoi posledovatelnosti povtoryayuschegosya fragmenta”, Diskretnaya optimizatsiya i issledovanie operatsii, Elektron. materialy Ros. konf., In-t matematiki SO RAN, Novosibirsk, 2007, 46–50 http://math.nsc.ru/conference/door07/DOOR_abstracts.pdf