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

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

1 Цитирования (Scopus)

Аннотация

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
Том100
Номер выпуска3
DOI
СостояниеОпубликовано - ноя 2019

Fingerprint Подробные сведения о темах исследования «NP-hardness of quadratic euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать