NP-hardness of quadratic euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes

A. V. Kel’manov, A. V. Pyatkin, V. I. Khandeev

Результат исследования: Научные публикации в периодических изданияхстатья


We consider the problem of clustering a finite set of N points in d-dimensional Euclidean space into two clusters minimizing the sum (over both clusters) of the intracluster sums of the squared distances between the cluster elements and their centers. The center of one cluster is defined as a centroid (geometric center). The center of the other cluster is determined as an optimized point in the input set. We analyze the variant of the problem with given cluster sizes such that their sum is equal to the size of the input set. The strong NP-hardness of this problem is proved.

Язык оригиналаанглийский
Страницы (с-по)545-548
Число страниц4
ЖурналDoklady Mathematics
Номер выпуска3
СостояниеОпубликовано - ноя 2019