Volume 17, No 5, 2010, P. 3745
UDC 519.2+621.391
A. V. Kel’manov, A. V. Pyatkin
NPcompleteness 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 NPcompleteness 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, NPcompleteness.
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
email: kelm@math.nsc.ru, artem@math.nsc.ru
