Kel’manov, A. V.; Pyatkin, A. V. On a variant of the problem of choosing a vector subset. (Russian) Zbl 1249.90343 Diskretn. Anal. Issled. Oper. 15, No. 5, 20-34 (2008). Summary: NP-completeness of the problem of choosing a subset of “similar” vectors, which is reduced to a variant of the problem of a posteriori (off-line) error correcting detection of a recurring numeric sequence in an unknown vector in the case of additive noise, is proved. A polynomial approximation algorithm for this problem with a guaranteed estimated accuracy in the case of fixed dimension is given. Cited in 1 Document MSC: 90C60 Abstract computational complexity for mathematical programming problems Keywords:choice of a vector subset; algorithmic complexity; NP-completeness; cluster analysis PDFBibTeX XMLCite \textit{A. V. Kel'manov} and \textit{A. V. Pyatkin}, Diskretn. Anal. Issled. Oper. 15, No. 5, 20--34 (2008; Zbl 1249.90343)