NP-completeness of some problems of choosing a vector subset
Alexander V. Kel’manov, A. V. Pyatkin · Journal of Applied and Industrial Mathematics · 2011
The NP-completeness is proved of some problems of choosing a Euclidean vector subset. One of the data analysis problems is reduced to these problems. The required subset is assumed to have a fixed cardinality and include the vectors that are “close” to each other by the criterium of the minimum sum of squares of distances.