NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters

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

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

Аннотация

We consider three related problems of partitioning an N-element set of points in d-dimensional Euclidean space into two clusters balancing the value of (1) the intracluster quadratic variance normalized by the cluster size in the first problem; (2) the intracluster quadratic variance in the second problem; and (3) the size-weighted intracluster quadratic variance in the third problem. The NP-completeness of all these problems is proved.

Язык оригиналаанглийский
Страницы (с-по)416-419
Число страниц4
ЖурналDoklady Mathematics
Том100
Номер выпуска2
DOI
СостояниеОпубликовано - 1 сен 2019

Fingerprint Подробные сведения о темах исследования «NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать