This article is cited in 1 paper

On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets

A. E. Galashov^a, A. V. Kel'manov<sup>ab

a</sup> Novosibirsk State University, Pirogova str., 2, Novosibirsk, 630090, Russia
^b Sobolev Institute of Mathematics, pr. Acad. Koptyug, 4, Novosibirsk, 630090, Russia

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.

Key words: Euclidean space, subsets search, clustering, NP-hard problem, exact pseudopolynomial-time algorithm.

UDC: 519.2+621.391

Received: 26.07.2016
Revised: 29.08.2016

DOI: 10.15372/SJNM20170102

 English version: Numerical Analysis and Applications, 2017, 10:1, 11–16

Bibliographic databases:

• 
• 
• 
•