Kel’manov, A. V. On the complexity of some data analysis problems. (Russian, English) Zbl 1224.93108 Zh. Vychisl. Mat. Mat. Fiz. 50, No. 11, 2045-2051 (2010); translation in Comput. Math., Math. Phys. 50, No. 11, 1941-1947 (2010). Summary: NP-completeness of certain discrete optimization problems is proved. These are the problems to which one can reduce some important problems arising in data analysis when certain subsets of vectors are sought. Cited in 7 Documents MSC: 93E10 Estimation and detection in stochastic control theory 68Q25 Analysis of algorithms and problem complexity 94A20 Sampling theory in information and communication theory Keywords:discrete optimization problem; complexity; NP-completeness; finding subsets of vectors in the Euclidean space; data analysis PDFBibTeX XMLCite \textit{A. V. Kel'manov}, Zh. Vychisl. Mat. Mat. Fiz. 50, No. 11, 2045--2051 (2010; Zbl 1224.93108); translation in Comput. Math., Math. Phys. 50, No. 11, 1941--1947 (2010) Full Text: DOI