Geodesic
A randomized algorithm for two-cluster partition of a set of vectors
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 2, pp. 335-344

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

A randomized algorithm is substantiated for the strongly NP-hard problem of partitioning a finite set of vectors of Euclidean space into two clusters of given sizes according to the minimum-of-the sum-of-squared-distances criterion. It is assumed that the centroid of one of the clusters is to be optimized and is determined as the mean value over all vectors in this cluster. The centroid of the other cluster is fixed at the origin. For an established parameter value, the algorithm finds an approximate solution of the problem in time that is linear in the space dimension and the input size of the problem for given values of the relative error and failure probability. The conditions are established under which the algorithm is asymptotically exact and runs in time that is linear in the space dimension and quadratic in the input size of the problem. 
@article{ZVMMF_2015_55_2_a16,
     author = {A. V. Kel'manov and V. I. Khandeev},
     title = {A randomized algorithm for two-cluster partition of a set of vectors},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {335--344},
     publisher = {mathdoc},
     volume = {55},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_2_a16/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - V. I. Khandeev
TI  - A randomized algorithm for two-cluster partition of a set of vectors
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2015
SP  - 335
EP  - 344
VL  - 55
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_2_a16/
LA  - ru
ID  - ZVMMF_2015_55_2_a16
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A V. I. Khandeev
%T A randomized algorithm for two-cluster partition of a set of vectors
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2015
%P 335-344
%V 55
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_2_a16/
%G ru
%F ZVMMF_2015_55_2_a16
A. V. Kel'manov; V. I. Khandeev. A randomized algorithm for two-cluster partition of a set of vectors. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 2, pp. 335-344. http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_2_a16/