On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line

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

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

Аннотация

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 clusters are given as input, while the other centers are defined as centroids (geometric centers). It is well known that the general case of the problem is strongly NP-hard. In this paper, we have shown that there exists an exact polynomial-time algorithm for the one-dimensional case of the problem.

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

Fingerprint Подробные сведения о темах исследования «On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать