NP-completeness of some problems of a vectors subset choice. (Russian) Zbl 1249.68080

Kel’manov, A. V.; Pyatkin, A. V.

Diskretn. Anal. Issled. Oper. 17, No. 5, 37-45 (2010).

Summary: The NP-completeness of some problems of selecting a subset of vectors in Euclidean space is proved. The solution of such problems leads to a problem in data analysis. It is assumed that the desired subset has a fixed cardinal number and includes vectors “close” to each other, i.e., of minimal sum of the squares of the distances.

MSC:

68Q17

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Keywords:

choice of a vector subset; clustering; algorithmic complexity; NP-completeness