Geodesic
Exact pseudopolinomial algorithms for a~balanced $2$-clustering problem
Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 3, pp. 21-34

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

We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the sizes of the clusters. The center of one cluster is given as input, while the center of the other cluster is unknown and determined as the average value over all points in the cluster (the geometric center). The two versions of the problems are analyzed in which the cluster sizes are either parts of the input or optimization variables. We present and prove exact pseudopolynomial algorithms in the case of integer components of the input points and fixed space dimension. Bibliogr. 24.
Keywords: Euclidean space, balanced clustering, NP-hardness, integer inputs, fixed space dimension
Mots-clés : exact pseudopolynomial algorithm. 
@article{DA_2016_23_3_a1,
     author = {A. V. Kel'manov and A. V. Motkova},
     title = {Exact pseudopolinomial algorithms for a~balanced $2$-clustering problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {21--34},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2016_23_3_a1/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - A. V. Motkova
TI  - Exact pseudopolinomial algorithms for a~balanced $2$-clustering problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2016
SP  - 21
EP  - 34
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2016_23_3_a1/
LA  - ru
ID  - DA_2016_23_3_a1
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A A. V. Motkova
%T Exact pseudopolinomial algorithms for a~balanced $2$-clustering problem
%J Diskretnyj analiz i issledovanie operacij
%D 2016
%P 21-34
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2016_23_3_a1/
%G ru
%F DA_2016_23_3_a1
A. V. Kel'manov; A. V. Motkova. Exact pseudopolinomial algorithms for a~balanced $2$-clustering problem. Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 3, pp. 21-34. http://geodesic.mathdoc.fr/item/DA_2016_23_3_a1/