zbMATH — the first resource for mathematics

On the complexity of a search for a subset of “similar” vectors. (English. Russian original) Zbl 1217.90142
Dokl. Math. 78, No. 1, 574-575 (2008); translation from Dokl. Akad. Nauk., Ross. Akad. Nauk. 421, No. 5, 590-592 (2008).
From the text: This paper deals with optimization problems in data analysis and pattern recognition. Specifically, we study a discrete optimization problem arising from a vector problem of off-line detection of a repeated fragment in a numerical sequence distorted by an additive noise. This problem has not been studied previously, and our goal is to analyze its complexity.

90C27 Combinatorial optimization
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI
[1] A. V. Kel’manov, Proceedings of XIII All-Russia Conference on Mathematical Methods in Pattern Recognition, Zelenogorsk, Leningrad oblast, September 30–October 6, 2007 (MAKS, Moscow, 2007).
[2] A. V. Kel’manov and B. A. Jeon, IEEE Trans. Signal Processing 52(3), 1–12 (2004). · doi:10.1109/TSP.2003.823069
[3] A. Wald, Sequential Analysis (Wiley, New York, 1947). · Zbl 0029.15805
[4] C. W. Helstrom, Elements of Signal Detection and Estimation (Prentice-Hall, Englewood Cliffs, N.J., 1979). · Zbl 0837.93067
[5] B. D. Anderson and J. D. Moore, Optimal Filtering (Prentice-Hall, Englewood Cliffs, N.J., 1995).
[6] I. V. Nikiforov, Sequential Change-Point Detection (Nauka, Moscow, 1983) [in Russian].
[7] A. A. Zhiglyavskii and A. E. Kraskovskii, Change-Point Detection in Radio Engineering (Leningr. Gos. Univ., Leningrad, 1988) [in Russian].
[8] N. Kligene and L. Telksnis, Avtom. Telemekh., No. 10, 5–56 (1983).
[9] F. Gini, A. Farina, and M. Greco, IEEE Trans. Aerospace Electron. Syst. 37, 329–359 (2001). · doi:10.1109/7.913696
[10] E. Kh. Gimadi, A. V. Kel’manov, M. A. Kel’manova, and S. A. Khamidullin, Sib. Zh. Ind. Mat. 9(1), 55–74 (2006).
[11] A. V. Kel’manov and S. A. Khamidullin, Comput. Math. Math. Phys. 41, 762–774 (2001) [Zh. Vychisl. Mat. Mat. Fiz. 41, 807–820 (2001)].
[12] A. V. Kel’manov, S. A. Khamidullin, and L. V. Okol’nishnikova, Pattern Recogn. Image Anal. 12, 438–447 (2002).
[13] A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, and A. V. Pyatkin, Diskret. Anal. Issled. Operatsii, Ser. 2 14 (1), 32–42 (2007).
[14] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, Calif., 1979). · Zbl 0411.68039
[15] P. Brucker, Lect. Notes Econ. Math. Syst. 157, 45–54 (1978). · doi:10.1007/978-3-642-95322-4_5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.