×

On a variant of the problem of choosing a vector subset. (Russian) Zbl 1249.90343

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.

MSC:

90C60 Abstract computational complexity for mathematical programming problems
PDFBibTeX XMLCite