On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets
A.E. Galashov1, A.V. Kel'manov1,2
1Novosibirsk State University, Pirogova st., 2, Novosibirsk, 630090, Russia
2Sobolev Institute of Mathematics, Acad. Koptyug avenue, 4, Novosibirsk, 630090, Russia
Keywords: поиск подмножеств, кластерный анализ, евклидово пространство, минимум суммы квадратов расстояний, NP-трудная задача, точный псевдополинимиальный алгоритм, Euclidean space, subsets search, clustering, NP-hard problem, exact pseudopolynomial-time algorithm
Abstract
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.
|
