Complexity of Some Problems of Quadratic Partitioning of 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 the intracluster quadratic variance normalized by the cluster size in the first problem, the intracluster quadratic variance in the second problem, and the size-weighted intracluster variance in the third problem. The NP-completeness of all these problems is proved.

Язык оригиналаанглийский
Страницы (с-по)163-170
Число страниц8
ЖурналComputational Mathematics and Mathematical Physics
Том60
Номер выпуска1
DOI
СостояниеОпубликовано - янв 2020

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

  • Цитировать