Geodesic
Fully polynomial-time approximation scheme for a~sequence $2$-clustering problem
Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 2, pp. 21-40

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

We consider a strongly NP-hard problem of partitioning a finite sequence of points in Euclidean space into two clusters minimizing the sum over both clusters of intra-cluster sum of squared distances from the clusters elements to their centers. The sizes of the clusters are fixed. The centroid of the first cluster is defined as the mean value of all vectors in the cluster, and the center of the second one is given in advance and is equal to 0. Additionally, the partition must satisfy the restriction that for all vectors in the first cluster the difference between the indices of two consequent points from this cluster is bounded from below and above by some given constants. We present a fully polynomial-time approximation scheme for the case of fixed space dimension. Bibliogr. 27.
Keywords: partitioning, sequence, Euclidean space, minimum sum-of-squared distances, NP-hardness, FPTAS. 
@article{DA_2016_23_2_a1,
     author = {A. V. Kel'manov and S. A. Khamidullin and V. I. Khandeev},
     title = {Fully polynomial-time approximation scheme for a~sequence $2$-clustering problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {21--40},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2016_23_2_a1/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - S. A. Khamidullin
AU  - V. I. Khandeev
TI  - Fully polynomial-time approximation scheme for a~sequence $2$-clustering problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2016
SP  - 21
EP  - 40
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2016_23_2_a1/
LA  - ru
ID  - DA_2016_23_2_a1
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A S. A. Khamidullin
%A V. I. Khandeev
%T Fully polynomial-time approximation scheme for a~sequence $2$-clustering problem
%J Diskretnyj analiz i issledovanie operacij
%D 2016
%P 21-40
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2016_23_2_a1/
%G ru
%F DA_2016_23_2_a1
A. V. Kel'manov; S. A. Khamidullin; V. I. Khandeev. Fully polynomial-time approximation scheme for a~sequence $2$-clustering problem. Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 2, pp. 21-40. http://geodesic.mathdoc.fr/item/DA_2016_23_2_a1/