Geodesic
Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 100-109

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

We consider the strongly $NP$-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given cardinalities under the minimum criterion for the sum over the clusters of the intracluster sums of squared distances from elements of the cluster to its center. It is assumed that the center of one of the clusters is given (without loss of generality, at the origin). The center of the second cluster is unknown and is determined as the mean value over all elements in this cluster. A polynomial-time approximation scheme (PTAS) is provided.
Keywords: ptas, cluster analysis, euclidean space, $np$-hard problem, ptas. 
@article{TIMM_2015_21_3_a10,
     author = {A. V. Dolgushev and A. V. Kel'manov and V. V. Shenmaier},
     title = {Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {100--109},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a10/}
}
TY  - JOUR
AU  - A. V. Dolgushev
AU  - A. V. Kel'manov
AU  - V. V. Shenmaier
TI  - Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2015
SP  - 100
EP  - 109
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a10/
LA  - ru
ID  - TIMM_2015_21_3_a10
ER  - 
%0 Journal Article
%A A. V. Dolgushev
%A A. V. Kel'manov
%A V. V. Shenmaier
%T Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
%J Trudy Instituta matematiki i mehaniki
%D 2015
%P 100-109
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a10/
%G ru
%F TIMM_2015_21_3_a10
A. V. Dolgushev; A. V. Kel'manov; V. V. Shenmaier. Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 100-109. http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a10/