Abstract:
We consider a strongly NP-hard Euclidean problem of finding a subsequence in a finite sequence. The criterion of the solution is a minimum sum of squared distances from the elements of a sought subsequence to its geometric center (centroid). It is assumed that a sought subsequence contains a given number of elements. In addition, a sought subsequence should satisfy the following condition: the difference between the indices of each previous and subsequent points is bounded with given lower and upper constants. We present an approximation algorithm of solving the problem and prove that it is a fully polynomial-time approximation scheme (FPTAS) when the space dimension is bounded by a constant.
Key words:
euclidean space, sequence, minimum sum of squared distances, NP-hardness, FPTAS.
Citation:
A. V. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “An approximation scheme for a problem of finding a subsequence”, Sib. Zh. Vychisl. Mat., 20:4 (2017), 379–392; Num. Anal. Appl., 10:4 (2017), 313–323
This publication is cited in the following 6 articles:
Anna Panasenko, Communications in Computer and Information Science, 2239, Mathematical Optimization Theory and Operations Research: Recent Trends, 2024, 349
A. Kel'manov, S. Khamidullin, V. Khandeev, A. Pyatkin, “Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence”, Ann. Math. Artif. Intell., 88:1-3 (2020), 157–168
Sergey Khamidullin, Vladimir Khandeev, Anna Panasenko, Lecture Notes in Computer Science, 12096, Learning and Intelligent Optimization, 2020, 96
Alexander Kel'manov, Sergey Khamidullin, Vladimir Khandeev, Artem Pyatkin, Lecture Notes in Computer Science, 11353, Learning and Intelligent Optimization, 2019, 326
A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, A. V. Pyatkin, Yu. V. Shamardin, V. V. Shenmaier, “A Polynomial-Time Approximation Algorithm for One Problem Simulating the Search in a Time Series for the Largest Subsequence of Similar Elements”, Pattern Recognit. Image Anal., 28:3 (2018), 363
Alexander Kel'manov, Artem Pyatkin, Sergey Khamidullin, Vladimir Khandeev, Yury V. Shamardin, Vladimir Shenmaier, Communications in Computer and Information Science, 871, Optimization Problems and Their Applications, 2018, 120