Abstract
We consider a strongly NP-hard Euclidean problem of finding a subsequence in a finite sequence. The criterion of the solution is the 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Kel’manov, A.V. and Pyatkin, A.V., On the Complexity of Some Problems of Choosing a Subsequence of Vectors, Zh. Vych. Mat. Mat. Fiz., 2012, vol. 52, no. 12, pp. 2284–2291.
Kel’manov, A.V., Romanchenko, S.M., and Khamidullin, S.A., Approximation Algorithms for Some Intractable Problems of Choosing a Vector Subsequence, J. Appl. Indust. Math., 2012, vol. 6, no. 4, pp. 443–450.
Kel’manov, A.V., Romanchenko, S.M., and Khamidullin, S.A., Exact Pseudopolynomial-Time Algorithms for Some Intractable Problems of Finding a Subsequence of Vectors, Zh. Vych. Mat. Mat. Fiz., 2013, vol. 53, no. 1, pp. 143–153.
Aggarwal, C.C., Data Mining: The Textbook, Springer, 2015.
Tak-chung, Fu., A Review on Time Series Data Mining, Engin. Appl. Artif. Intell., 2011, vol. 24, iss. 11, pp. 164–181.
Kuenzer, C., Dech, S., and Wagner, W., Remote Sensing Time Series. Remote Sensing and Digital Image Processing, vol. 22, Switzerland: Springer, 2015.
Warren, Liao T., Clustering of Time Series Data—A Survey, Patt. Recogn., 2005, vol. 38, no. 11, pp. 1857–1874.
Kel’manov, A.V. and Pyatkin, A.V., NP-Completeness of Some Problems of Choosing a Vector Subset, J. Appl. Indust. Math., 2011, vol. 5, no. 3, pp. 352–357.
Aggarwal, A., Imai, H., Katoh, N., and Suri, S., Finding k Points with Minimum Diameter and Related Problems, J. Algor., 1991, vol. 12, pp. 38–56.
Kel’manov, A.V. and Romanchenko, S.M., An Approximation Algorithm for Solving a Problem of Search for a Vector Subset, J. Appl. Indust. Math., 2012, vol. 6, no. 1, pp. 90–96.
Shenmaier, V.V., An Approximation Scheme for a Problem of Search for a Vector Subset, J. Appl. Indust. Math., 2012, vol. 6, no. 3, pp. 381–386.
Kel’manov, A.V. and Romanchenko, S.M., Pseudopolynomial Algorithms for Certain Computationally Hard Vector Subset and Cluster Analysis Problems, Automat. Remote Control, 2012, vol. 73, no. 2, pp. 349–354.
Kel’manov, A.V. and Romanchenko, S.M., An FPTAS for a Vector Subset Search Problem, J. Appl. Indust. Math., 2014, vol. 8, no. 3, pp. 329–336.
Kel’manov, A.V. and Khamidullin, S.A., Posterior Detection of a Given Number of Identical Subsequences in a Quasi-Periodic Sequence, Comput. Math. Math. Phys., 2001, vol. 41, no. 5, pp. 762–774.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kel’manov, A.V., Romanchenko, S.M. & Khamidullin, S.A. An Approximation Scheme for the Problem of Finding a Subsequence. Numer. Analys. Appl. 10, 313–323 (2017). https://doi.org/10.1134/S1995423917040036
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1995423917040036