Pseudo-polynomial Algorithms for Some Problems of Searching for the Largest Subsets

We consider several problems of finding the subsets with the largest minimal cardinality and limited scatter in a finite set of points in Euclidean space. For each cluster, the scatter is the sum of the distances (raised to a power) between the elements and the center of the cluster. Depending on the problem, the center can be defined in different ways—as a fixed point, as the centroid of the cluster, etc. We propose a general scheme for a pseudo-polynomial algorithm to solve such problems, and we also show how and in what time this scheme can be implemented for several types of centers.