Volume 15, No 5, 2008, P. 20-34
UDC 519.2+621.391
A. V. Kel’manov, A. V. Pyatkin
On one variant of the vectors subset choice problem
Abstract:
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.
Keywords: numerical vector sequence, a posteriori processing, repeating vector, optimal noise proof detecting, complexity, NP-completeness, approximation algorithm.
Kel’manov Alexander Vasilyevich 1
Pyatkin Artem Valeryevich 1
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: kelm@math.nsc.ru, artem@math.nsc.ru
