TY - JOUR

T1 - Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets

AU - Galashov, A. E.

AU - Kel’manov, A. V.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - In this paper, a strongly NP-hard problem of finding a family of disjoint subsets with given cardinalities in a finite set of points from a Euclidean space is considered. Minimization 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 the search criterion. It is 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), the problem is a pseudopolynomial time solvable one.

AB - In this paper, a strongly NP-hard problem of finding a family of disjoint subsets with given cardinalities in a finite set of points from a Euclidean space is considered. Minimization 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 the search criterion. It is 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), the problem is a pseudopolynomial time solvable one.

KW - clustering

KW - Euclidean space

KW - exact pseudopolynomial time algorithm

KW - NP-hard problem

KW - subsets search

UR - http://www.scopus.com/inward/record.url?scp=85014770273&partnerID=8YFLogxK

U2 - 10.1134/S1995423917010025

DO - 10.1134/S1995423917010025

M3 - Article

AN - SCOPUS:85014770273

VL - 10

SP - 11

EP - 16

JO - Numerical Analysis and Applications

JF - Numerical Analysis and Applications

SN - 1995-4239

IS - 1

ER -