Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem
- Авторлар: Kel’manov A.V.1,2, Khandeev V.I.1,2
-
Мекемелер:
- Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
- Novosibirsk State University
- Шығарылым: Том 59, № 9 (2019)
- Беттер: 1553-1561
- Бөлім: Article
- URL: https://journal-vniispk.ru/0965-5425/article/view/180812
- DOI: https://doi.org/10.1134/S0965542519090112
- ID: 180812
Дәйексөз келтіру
Аннотация
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
Қосымша файлдар
