Geodesic
Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 2, pp. 332-340

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

The strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given sizes (cardinalities) minimizing the sum (over both clusters) of the intracluster sums of squared distances from the elements of the clusters to their centers is considered. It is assumed that the center of one of the sought clusters is specified at the desired (arbitrary) point of space (without loss of generality, at the origin), while the center of the other one is unknown and determined as the mean value over all elements of this cluster. It is shown that unless P = NP, there is no fully polynomial-time approximation scheme for this problem, and such a scheme is substantiated in the case of a fixed space dimension. 
@article{ZVMMF_2016_56_2_a13,
     author = {A. V. Kel'manov and V. I. Khandeev},
     title = {Fully polynomial-time approximation scheme for a special case of a quadratic {Euclidean} 2-clustering problem},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {332--340},
     publisher = {mathdoc},
     volume = {56},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_2_a13/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - V. I. Khandeev
TI  - Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2016
SP  - 332
EP  - 340
VL  - 56
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_2_a13/
LA  - ru
ID  - ZVMMF_2016_56_2_a13
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A V. I. Khandeev
%T Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2016
%P 332-340
%V 56
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_2_a13/
%G ru
%F ZVMMF_2016_56_2_a13
A. V. Kel'manov; V. I. Khandeev. Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 2, pp. 332-340. http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_2_a13/