An Approximation Scheme for the Problem of Finding a Subsequence
- Authors: Kel’manov A.V.1,2, Romanchenko S.M.1, Khamidullin S.A.1
-
Affiliations:
- Sobolev Institute of Mathematics
- Novosibirsk State University
- Issue: Vol 10, No 4 (2017)
- Pages: 313-323
- Section: Article
- URL: https://journals.rcsi.science/1995-4239/article/view/198020
- DOI: https://doi.org/10.1134/S1995423917040036
- ID: 198020
Cite item
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.
About the authors
A. V. Kel’manov
Sobolev Institute of Mathematics; Novosibirsk State University
Author for correspondence.
Email: kelm@math.nsc.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 1, Novosibirsk, 630090
S. M. Romanchenko
Sobolev Institute of Mathematics
Email: kelm@math.nsc.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090
S. A. Khamidullin
Sobolev Institute of Mathematics
Email: kelm@math.nsc.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090