This article is cited in 10 papers

On the complexity of some data analysis problems

A. V. Kel'manov

Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, pr. Akademika Koptyuga 4, Novosibirsk, 630090 Russia

Abstract: 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.

Key words: discrete optimization problem, complexity, NP-completeness, finding subsets of vectors in the Euclidean space, data analysis.

UDC: 519.7

Received: 14.01.2010
Revised: 16.06.2010

 English version: Computational Mathematics and Mathematical Physics, 2010, 50:11, 1941–1947

Bibliographic databases:

• 
• 
•