Open AccessNP-hardness of quadratic Euclidean 1-Mean and 1-Median 2-Clustering problem with the constraints on the cluster sizes
Author(s) -
А. В. Кельманов,
A. V. Pyatkin,
В. И. Хандеев
Publication year - 2019
Publication title -
doklady akademii nauk. rossijskaâ akademiâ nauk
Language(s) - English
Resource type - Journals
ISSN - 0869-5652
DOI - 10.31857/s0869-56524894339-343
Subject(s) - cluster analysis , cluster (spacecraft) , euclidean space , centroid , combinatorics , mathematics , center (category theory) , point (geometry) , set (abstract data type) , quadratic equation , euclidean geometry , euclidean distance , computer science , geometry , statistics , chemistry , crystallography , programming language
In the paper, we consider a problem of clustering a finite set of N points in d-dimensional Euclidean space into two clusters minimizing the sum over all clusters of the intracluster sums of the distances between clusters elements and their centers. The center of one cluster is defined as centroid (geometric center). The center of the other one is a sought point in the input set. We analyze the variant of the problem with the given clusters sizes. We have proved the strong NP-hardness of this problem.