Geodesic
On one variant of the vectors subset choice problem
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 5, pp. 20-34.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2008_15_5_a2,
     author = {A. V. Kel'manov and A. V. Pyatkin},
     title = {On one variant of the vectors subset choice problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {20--34},
     publisher = {mathdoc},
     volume = {15},
     number = {5},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_5_a2/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - A. V. Pyatkin
TI  - On one variant of the vectors subset choice problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 20
EP  - 34
VL  - 15
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_5_a2/
LA  - ru
ID  - DA_2008_15_5_a2
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A A. V. Pyatkin
%T On one variant of the vectors subset choice problem
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 20-34
%V 15
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2008_15_5_a2/
%G ru
%F DA_2008_15_5_a2
A. V. Kel'manov; A. V. Pyatkin. On one variant of the vectors subset choice problem. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 5, pp. 20-34. http://geodesic.mathdoc.fr/item/DA_2008_15_5_a2/

[1] Baburin A. E., Gimadi E. Kh., Glebov N. I., Pyatkin A. V., “Zadacha otyskaniya podmnozhestva vektorov s maksimalnym summarnym vesom”, Diskret. analiz i issled. operatsii. Ser. 2, 14:1 (2007), 32–42 | MR

[2] Gimadi E. Kh., Kelmanov A. V., Kelmanova M. A., Khamidullin S. A., “Aposteriornoe obnaruzhenie v chislovoi posledovatelnosti kvaziperiodicheskogo fragmenta pri zadannom chisle povtorov”, Sib. zhurn. industr. matematiki, 9:1 (2006), 55–74 | MR

[3] Kelmanov A. V., “O nekotorykh polinomialno razreshimykh i NP-trudnykh zadachakh analiza i raspoznavaniya posledovatelnostei s kvaziperiodicheskoi strukturoi”, Sb. dokl. 13-i Vseross. konf. “Matematicheskie metody raspoznavaniya obrazov” (Zelenogorsk, 30 sentyabrya–6 oktyabrya 2007), MAKS Press, M., 2007, 261–264

[4] Kelmanov A. V., “Polinomialno razreshimye i NP-trudnye varianty zadachi optimalnogo obnaruzheniya v chislovoi posledovatelnosti povtoryayuschegosya fragmenta”, Materialy Rossiiskoi konf. “Diskretnaya optimizatsiya i issledovanie operatsii” (Vladivostok, 7–14 sentyabrya 2007), Izd-vo In-ta matematiki, Novosibirsk, 2007, 46–50; http: math.nsc.ru/conference/door07/DOOR_abstracts.pdf

[5] Kelmanov A. V., Khamidullin S. A., “Aposteriornoe obnaruzhenie zadannogo chisla odinakovykh podposledovatelnostei v kvaziperiodicheskoi posledovatelnosti”, Zhurn. vychisl. matematiki i mat. fiziki, 41:5 (2001), 807–820 | MR

[6] Aloise D., Hansen P., “On the complexity of minimum sum-of-squares clustering”, Les Cahiers du GERAD, G-2007-50, 2007, 12 pp.

[7] Drineas P., Frieze A., Kannan R., Vempala S., Vinay V., “Clustering large graphs via the singular value decomposition”, Machine Learning, 56 (2004), 9–33 | DOI | Zbl

[8] Garey M. R., Johnson D. S., Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, CA, 1979, 340 pp. | MR | Zbl

[9] Kel'manov A. V., Jeon B., “A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train”, IEEE Transactions on Signal Processing, 52:3 (2004), 1–12 | DOI | MR

[10] Kel'manov A. V., Khamidullin S. A., Okol'nishnikova L. V., “A posteriori detection of identical subsequences in a quasiperiodic sequence”, Pattern Recognition and Image Analysis, 12:4 (2002), 438–447 | MR

[11] MacQueen J., “Some methods for classification and analysis of multivariate observations”, Proc. Fifth Berkeley Symp. Math. Statistics and Probability, Vol. I: Statistics, Univ. Berkeley Press, Berkeley, CA, 1967, 281–296 | MR

[12] Wald A., Sequential analysis, John Wiley, New York, 1947, 230 pp. | MR

[13] http: math.nsc.ru/~serge/qpsl/