Geodesic
An exact pseudopolynomial algorithm for a~bi-partitioning problem
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 4, pp. 50-62

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 vectors into two sets (clusters) under the criterion of minimum sum-of-squared distances from the elements of clusters to their centers. The center of the first cluster is the average value of the vectors in the cluster, and the center of the second one is the origin. We prove that the problem is solvable in polynomial time in the case of fixed space dimension. We also present a pseudopolynomial algorithm which finds an optimal solution in the case of integer values of the components of the vectors in the input set and fixed space dimension. Bibliogr. 27.
Keywords: bi-partitioning, vector subset, squared Euclidean distances, NP-hardness
Mots-clés : exact pseudopolynomial algorithm. 
@article{DA_2015_22_4_a3,
     author = {A. V. Kel'manov and V. I. Khandeev},
     title = {An exact pseudopolynomial algorithm for a~bi-partitioning problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {50--62},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_4_a3/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - V. I. Khandeev
TI  - An exact pseudopolynomial algorithm for a~bi-partitioning problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 50
EP  - 62
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_4_a3/
LA  - ru
ID  - DA_2015_22_4_a3
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A V. I. Khandeev
%T An exact pseudopolynomial algorithm for a~bi-partitioning problem
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 50-62
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_4_a3/
%G ru
%F DA_2015_22_4_a3
A. V. Kel'manov; V. I. Khandeev. An exact pseudopolynomial algorithm for a~bi-partitioning problem. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 4, pp. 50-62. http://geodesic.mathdoc.fr/item/DA_2015_22_4_a3/