|
This article is cited in 1 scientific paper (total in 1 paper)
Polynomial-time solvability of the one-dimensional case of an NP-hard clustering problem
A. V. Kel'manovab, V. I. Khandeevab a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, 630090 Russia
b Novosibirsk State University, Novosibirsk, 630090 Russia
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.
Key words:
Euclidean space, clustering, partitioning, minimum sum-of-squares, strongly NP-hard problem, one-dimensional case, polynomial-time solvability.
Received: 03.04.2019 Revised: 03.04.2019 Accepted: 15.05.2019
Citation:
A. V. Kel'manov, V. I. Khandeev, “Polynomial-time solvability of the one-dimensional case of an NP-hard clustering problem”, Zh. Vychisl. Mat. Mat. Fiz., 59:9 (2019), 1617–1625; Comput. Math. Math. Phys., 59:9 (2019), 1553–1561
Linking options:
https://www.mathnet.ru/eng/zvmmf10959 https://www.mathnet.ru/eng/zvmmf/v59/i9/p1617
|
Statistics & downloads: |
Abstract page: | 115 | References: | 13 |
|