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

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. 
@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},
     publisher = {mathdoc},
     volume = {57},
     number = {8},
     year = {2017},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_8_a11/
%G ru
%F ZVMMF_2017_57_8_a11
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/