RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2010 Volume 17, Issue 5, Pages 37–45 (Mi da623)

This article is cited in 40 papers

NP-completeness of some problems of a vectors subset choice

A. V. Kel'manovab, A. V. Pyatkinab

a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia

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.

UDC: 519.2+621.391

Received: 12.04.2010
Revised: 06.07.2010


 English version:
Journal of Applied and Industrial Mathematics, 2011, 5:3, 352–357

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025