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


Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

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.

Авторлар туралы

A. Kel’manov

Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University

Хат алмасуға жауапты Автор.
Email: kelm@math.nsc.ru
Ресей, Novosibirsk, 630090; Novosibirsk, 630090

V. Khandeev

Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University

Хат алмасуға жауапты Автор.
Email: khandeev@math.nsc.ru
Ресей, Novosibirsk, 630090; Novosibirsk, 630090

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML

© Pleiades Publishing, Ltd., 2019