Volume 17, No 5, 2010, P. 37-45
A. V. Kel’manov, A. V. Pyatkin
NP-completeness of some problems of a vectors subset choice
One of the problem in data analysis reduces to problems of a vectors subset selection. The NP-completeness of these problems is proved. These problems are connected with searching a vector subset in a given set in Euclidian space under following conditions. The first condition is that the required subset has a given cardinality, and the second one is that this subset includes vectors which are close to each other under the criterion of minimum sum of squared distances.
Keywords: choice of a vector subset, clustering, algorithmic complexity, NP-completeness.
Kel’manov Alexander Vasilyevich 1,2
Pyatkin Artem Valerievich 1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: firstname.lastname@example.org, email@example.com