Geodesic
On pseudopolynomial-time solvability of a~quadratic Euclidean problem of finding a~family of disjoint subsets
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 20 (2017) no. 1, pp. 15-22

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

We consider a strongly NP-hard problem of finding a family of disjoint subsets with given cardinalities in a finite set of points from the Euclidean space. A minimum of the sum over all required subsets of the sum of the squared distances from the elements of these subsets to their geometric centers is used as a search criterion. We have proved that if the coordinates of the input points are integer, and the space dimension and the number of required subsets are fixed (i.e. bounded by some constants), then the problem is a pseudopolynomial-time solvable one. 
@article{SJVM_2017_20_1_a1,
     author = {A. E. Galashov and A. V. Kel'manov},
     title = {On pseudopolynomial-time solvability of a~quadratic {Euclidean} problem of finding a~family of disjoint subsets},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {15--22},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2017_20_1_a1/}
}
TY  - JOUR
AU  - A. E. Galashov
AU  - A. V. Kel'manov
TI  - On pseudopolynomial-time solvability of a~quadratic Euclidean problem of finding a~family of disjoint subsets
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2017
SP  - 15
EP  - 22
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJVM_2017_20_1_a1/
LA  - ru
ID  - SJVM_2017_20_1_a1
ER  - 
%0 Journal Article
%A A. E. Galashov
%A A. V. Kel'manov
%T On pseudopolynomial-time solvability of a~quadratic Euclidean problem of finding a~family of disjoint subsets
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2017
%P 15-22
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJVM_2017_20_1_a1/
%G ru
%F SJVM_2017_20_1_a1
A. E. Galashov; A. V. Kel'manov. On pseudopolynomial-time solvability of a~quadratic Euclidean problem of finding a~family of disjoint subsets. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 20 (2017) no. 1, pp. 15-22. http://geodesic.mathdoc.fr/item/SJVM_2017_20_1_a1/