This article is cited in 4 scientific papers (total in 4 papers)
On one problem of searching for tuples of fragments in a numerical sequence
A. V. Kel'manov, L. V. Mikhaylova, S. A. Khamidullin
S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
A discrete optimization problem is considered to which the problem of the noise-proof detection of the recurring tuple of fragments in a numerical sequence is reduced. A variant of the problem in which the fragments from the desired tuples coincide (in the noiseless case) with the elements of the given tuple of vectors is analyzed. A new exact polynomial algorithm for solving this special optimization problem is proved. This algorithm provides that the solution is optimal under the minimum sum-of-squared deviations criterion. If noise is additive and it is a Gaussian sequence of independent identically distributed variables, then the solution is optimal under the maximum likelihood criterion as well. The time complexity of our algorithm is proved to be less then the complexity of the previously known algorithm. Bibl. 4.
discrete optimization problem, numerical sequence, recurring tuple of fragments, off-line algorithm.
PDF file (286 kB)
A. V. Kel'manov, L. V. Mikhaylova, S. A. Khamidullin, “On one problem of searching for tuples of fragments in a numerical sequence”, Diskretn. Anal. Issled. Oper., 16:4 (2009), 31–46
Citation in format AMSBIB
\by A.~V.~Kel'manov, L.~V.~Mikhaylova, S.~A.~Khamidullin
\paper On one problem of searching for tuples of fragments in a~numerical sequence
\jour Diskretn. Anal. Issled. Oper.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
A. V. Kel'manov, S. M. Romanchenko, S. A. Khamidullin, “Approximation algorithms for some NP-hard problems of searching a vectors subsequence”, J. Appl. Industr. Math., 6:4 (2012), 443–450
A. V. Kelmanov, A. V. Pyatkin, “O slozhnosti nekotorykh zadach vybora podposledovatelnosti vektorov”, Zh. vychisl. matem. i matem. fiz., 52:12 (2012), 2284–2291
A. V. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “Tochnye psevdopolinomialnye algoritmy dlya nekotorykh trudnoreshaemykh zadach poiska podposledovatelnosti vektorov”, Zh. vychisl. matem. i matem. fiz., 53:1 (2013), 143–153
A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some vector sequence clustering problems”, J. Appl. Industr. Math., 7:3 (2013), 363–369
|Number of views:|