Geodesic
An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 3, pp. 144-152 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We consider the problem of partitioning a finite sequence of points in Euclidean space into a given number of clusters (subsequences) minimizing the sum over all clusters of intracluster sums of squared distances from elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is specified at the origin, while the centers of the other clusters are unknown. Very unknown cluster center is defined as the mean value of cluster elements. Additionally, there are a few structural constraints on the elements of the sequence that enter the clusters with unknown centers: (1) the concatenation of indices of elements of these clusters is an increasing sequence, (2) the difference between two consequent indices is bounded from below and above by prescribed constants, and (3) the total number of elements in these clusters is given as an input. It is shown that the problem is strongly NP-hard. A 2-approximation algorithm that is polynomial for a fixed number of clusters is proposed for this problem.
Keywords: partitioning, sequence, Euclidean space, minimum sum of squared distances, NP-hardness, approximation algorithm. 
@article{TIMM_2016_22_3_a13,
     author = {A. V. Kel'manov and L. V. Mikhailova and S. A. Khamidullin and V. I. Khandeev},
     title = {An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {144--152},
     year = {2016},
     volume = {22},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a13/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - L. V. Mikhailova
AU  - S. A. Khamidullin
AU  - V. I. Khandeev
TI  - An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2016
SP  - 144
EP  - 152
VL  - 22
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a13/
LA  - ru
ID  - TIMM_2016_22_3_a13
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A L. V. Mikhailova
%A S. A. Khamidullin
%A V. I. Khandeev
%T An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities
%J Trudy Instituta matematiki i mehaniki
%D 2016
%P 144-152
%V 22
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a13/
%G ru
%F TIMM_2016_22_3_a13
A. V. Kel'manov; L. V. Mikhailova; S. A. Khamidullin; V. I. Khandeev. An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 3, pp. 144-152. http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a13/

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

[2] Remote sensing time series: Revealing Land Surface Dynamics, Remote Sensing and Digital Image Processing, 22, eds. C. Kuenzer, S. Dech, W. Wagner, Springer International Publishing, New York etc., 2015, 441 pp.

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

[4] Aggarwal C.C., Data mining: The textbook, Springer International Publishing, New York etc., 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 | MR | Zbl

[6] Kelmanov A.V., Khamidullin S.A., “Priblizhennyi algoritm dlya odnoi zadachi razbieniya posledovatelnosti”, Diskretnyi analiz i issledovanie operatsii, 21:1 (2014), 53–66 | MR | Zbl

[7] Kelmanov A.V., Mikhailova L.V., “Sovmestnoe obnaruzhenie v kvaziperiodicheskoi posledovatelnosti zadannogo chisla fragmentov iz etalonnogo nabora i ee razbienie na uchastki, vklyuchayuschie serii odinakovykh fragmentov”, Zhurn. vychisl. matematiki i mat. fiziki, 46:1 (2006), 172–189 | MR | Zbl

[8] Kelmanov A.V., Khamidullin S.A., Khandeev V.I., “Tochnyi psevdopolinomialnyi algoritm dlya odnoi zadachi biklasterizatsii posledovatelnosti”, XV Vseross. konf. “Matematicheskoe programmirovanie i prilozheniya”, tez. dokl., IMM UrO RAN, Ekaterinburg, 2015, 139

[9] Kelmanov A.V., Khamidullin S.A., Khandeev V.I., “Polnostyu polinomialnaya approksimatsionnaya skhema dlya odnoi zadachi dvukhklasternogo razbieniya posledovatelnosti”, Diskretnyi analiz i issledovanie operatsii, 23:2 (2016), 21–40 | MR | Zbl

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