Geodesic
Approximation algorithm for the problem of partitioning a sequence into clusters
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 8, pp. 1392-1400 
A. V. Kel'manov; L. V. Mikhailova; S. A. Khamidullin; V. I. Khandeev. Approximation algorithm for the problem of partitioning a sequence into clusters. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 8, pp. 1392-1400. http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_8_a11/
@article{ZVMMF_2017_57_8_a11,
     author = {A. V. Kel'manov and L. V. Mikhailova and S. A. Khamidullin and V. I. Khandeev},
     title = {Approximation algorithm for the problem of partitioning a sequence into clusters},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1392--1400},
     year = {2017},
     volume = {57},
     number = {8},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_8_a11/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - L. V. Mikhailova
AU  - S. A. Khamidullin
AU  - V. I. Khandeev
TI  - Approximation algorithm for the problem of partitioning a sequence into clusters
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2017
SP  - 1392
EP  - 1400
VL  - 57
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_8_a11/
LA  - ru
ID  - ZVMMF_2017_57_8_a11
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A L. V. Mikhailova
%A S. A. Khamidullin
%A V. I. Khandeev
%T Approximation algorithm for the problem of partitioning a sequence into clusters
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2017
%P 1392-1400
%V 57
%N 8
%U http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_8_a11/
%G ru
%F ZVMMF_2017_57_8_a11

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

We consider the problem of partitioning a finite sequence of Euclidean points into a given number of clusters (subsequences) using the criterion of the minimal sum (over all clusters) of intercluster sums of squared distances from the elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is at the origin, while the center of each of the other clusters is unknown and determined as the mean value over all elements in this cluster. Additionally, the partition obeys two structural constraints on the indices of sequence elements contained in the clusters with unknown centers: (1) the concatenation of the indices of elements in these clusters is an increasing sequence, and (2) the difference between an index and the preceding one is bounded above and below by prescribed constants. It is shown that this problem is strongly NP-hard. A 2-approximation algorithm is constructed that is polynomial-time for a fixed number of clusters.

[1] Tak-chung Fu, “A review on time series data mining”, Eng. Appl. Artificial Intelligence, 24:1 (2011), 164–181 | DOI

[2] Kuenzer C., Dech S., Wagner W., Remote sensing time series, Remote Sensing and Digital Image Processing, 22, Springer, Switzerland, 2015, 441 pp. | DOI

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

[4] Aggarwal C. C., Data Mining: The Textbook, Springer, Berlin, 2015, 734 pp. | MR | Zbl

[5] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach klasternogo analiza vektornykh posledovatelnostei”, Diskretnyi analiz i issledovanie operatsii, 20:2 (2013), 47–57

[6] Kelmanov A. V., Khamidullin S. A., “Priblizhennyi polinomialnyi algoritm dlya odnoi zadachi bikla-sterizatsii posledovatelnosti”, Zh. vychisl. matem. i matem. fiz., 55:6 (2015), 1076–1085 | DOI | Zbl

[7] Kelmanov A. V., Mikhailova L. V., “Aposteriornoe obnaruzhenie kvaziperiodicheskikh fragmentov iz etalonnogo nabora v chislovoi posledovatelnosti i ee razbienie na uchastki, vklyuchayuschie serii odinakovykh fragmentov”, Zh. vychisl. matem. i matem. fiz., 48:5 (2008), 899–915 | Zbl

[8] Kelmanov A. V., Romanchenko S. M., “FPTAS dlya odnoi zadachi poiska podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 21:3 (2014), 41–52