Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem

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

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

Аннотация

Abstract: We consider the problem of partitioning a finite set of points in Euclidean space into clusters so as to minimize the sum, over all clusters, of the intracluster sums of the squared distances between cluster elements and their centers. The centers of some of the clusters are given as an input, while the centers of the others are determined as centroids (geometric centers). It is known that, in the general case, this problem is strongly NP-hard. We prove constructively that the one-dimensional case of this problem is solvable in polynomial time.

Язык оригиналаанглийский
Страницы (с-по)1553-1561
Число страниц9
ЖурналComputational Mathematics and Mathematical Physics
Том59
Номер выпуска9
DOI
СостояниеОпубликовано - 1 сен 2019

Fingerprint Подробные сведения о темах исследования «Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать