On the complexity of a search for a subset of “similar” vectors. (English. Russian original) Zbl 1217.90142

Kel’manov, A. V.; Pyatkin, A. V.

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.

MSC:

90C27	Combinatorial optimization
90C60	Abstract computational complexity for mathematical programming problems

References:

[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