Geodesic
An approximation scheme for a problem of finding a subsequence
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 20 (2017) no. 4, pp. 379-392 
A. V. Kelmanov; S. M. Romanchenko; S. A. Khamidullin. An approximation scheme for a problem of finding a subsequence. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 20 (2017) no. 4, pp. 379-392. http://geodesic.mathdoc.fr/item/SJVM_2017_20_4_a2/
@article{SJVM_2017_20_4_a2,
     author = {A. V. Kelmanov and S. M. Romanchenko and S. A. Khamidullin},
     title = {An approximation scheme for a~problem of finding a~subsequence},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {379--392},
     year = {2017},
     volume = {20},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2017_20_4_a2/}
}
TY  - JOUR
AU  - A. V. Kelmanov
AU  - S. M. Romanchenko
AU  - S. A. Khamidullin
TI  - An approximation scheme for a problem of finding a subsequence
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2017
SP  - 379
EP  - 392
VL  - 20
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/SJVM_2017_20_4_a2/
LA  - ru
ID  - SJVM_2017_20_4_a2
ER  - 
%0 Journal Article
%A A. V. Kelmanov
%A S. M. Romanchenko
%A S. A. Khamidullin
%T An approximation scheme for a problem of finding a subsequence
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2017
%P 379-392
%V 20
%N 4
%U http://geodesic.mathdoc.fr/item/SJVM_2017_20_4_a2/
%G ru
%F SJVM_2017_20_4_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach vybora podposledovatelnosti vektorov”, Zhurn. vychisl. matem. i mat. fiziki, 52:12 (2012), 2284–2291 | Zbl

[2] Kel'manov A. V., Romanchenko S. M., Khamidullin S. A., “Approximation algorithms for some intractable problems of choosing a vector subsequence”, J. Appl. Indust. Math., 6:4 (2012), 443–450 | DOI | MR | Zbl

[3] Kelmanov A. V., Romanchenko S. M., Khamidullin S. A., “Tochnye psevdopolinomialnye algoritmy dlya nekotorykh trudnoreshaemykh zadach poiska podposledovatelnosti vektorov”, Zhurn. vychisl. matem. i mat. fiziki, 53:1 (2013), 143–153 | DOI | Zbl

[4] Aggarwal C. C., Data Mining: The Textbook, Springer International Publishing, 2015 | MR | Zbl

[5] Tak-chung Fu., “A review on time series data mining”, Engineering Applications of Artificial Intelligence, 24:11 (2011), 164–181

[6] Kuenzer C., Dech S., Wagner W., Remote Sensing Time Series, Remote Sensing and Digital Image Processing, 22, Springer International Publishing, Switzerland, 2015 | DOI

[7] Warren Liao T., “Clustering of time series data – a survey”, Pattern Recognition, 38:11 (2005), 1857–1874 | DOI | Zbl

[8] Kel'manov A. V., Pyatkin A. V., “NP-completeness of some problems of choosing a vector subset”, J. Appl. Indust. Math., 5:3 (2011), 352–357 | DOI | MR | Zbl

[9] Aggarwal A., Imai H., Katoh N., Suri S., “Finding $k$ points with minimum diameter and related problems”, J. Algorithms, 12 (1991), 38–56 | DOI | MR | Zbl

[10] Kel'manov A. V., Romanchenko S. M., “An approximation algorithm for solving a problem of search for a vector subset”, J. Appl. Indust. Math., 6:1 (2012), 90–96 | DOI | MR | Zbl

[11] Shenmaier V. V., “An approximation scheme for a problem of search for a vector subset”, J. Appl. Indust. Math., 6:3 (2012), 381–386 | DOI | MR | Zbl

[12] Kel'manov A. V., Romanchenko S. M., “Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems”, Automation and Remote Control, 73:2 (2012), 349–354 | DOI | MR | Zbl

[13] Kel'manov A. V., Romanchenko S. M., “An FPTAS for a vector subset search problem”, J. Appl. Indust. Math., 8:3 (2014), 329–336 | DOI | MR | Zbl

[14] Kel'manov A. V., Khamidullin S. A., “Posterior detection of a given number of identical subsequences in a quasi-periodic sequence”, Comput. Mathem. and Math. Phys., 41:5 (2001), 762–774 | MR | Zbl