×

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.

MSC:

93E10 Estimation and detection in stochastic control theory
68Q25 Analysis of algorithms and problem complexity
94A20 Sampling theory in information and communication theory
PDFBibTeX XMLCite
Full Text: DOI