On one variant of the vectors subset choice problem

One variant of the problem of a posteriori (off-line) noise proof search for the unknown repeating vector in the case, when the noise is additive, can be reduced to the “similar” vectors subset choice problem. This problem is proved to be NP-complete. A polynomial approximation algorithm with guaranteed relative error bounds in the case of the fixed dimension of the space is suggested for this problem. Bibl. 13.