×

zbMATH — the first resource for mathematics

NP-completeness of some problems of a vectors subset choice. (Russian) Zbl 1249.68080
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.)
PDF BibTeX XML Cite