Volume 17, No 5, 2010, P. 37-45

UDC 519.2+621.391
A. V. Kel’manov, A. V. Pyatkin
NP-completeness of some problems of a vectors subset choice

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

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
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: kelm@math.nsc.ru, artem@math.nsc.ru