Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
The Problem K-Means and Given J-Centers : Polynomial Solvability in One Dimension. / Kel’manov, Alexander; Khandeev, Vladimir.
Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. ред. / Igor Bykadorov; Vitaly Strusevich; Tatiana Tchemisova. Springer International Publishing AG, 2019. стр. 207-216 (Communications in Computer and Information Science; Том 1090 CCIS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - The Problem K-Means and Given J-Centers
T2 - 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
AU - Kel’manov, Alexander
AU - Khandeev, Vladimir
N1 - Publisher Copyright: © 2019, Springer Nature Switzerland AG.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - We consider a 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 clusters elements and their centers. The centers of one part of the clusters are given as an input, while the centers of the other part of the clusters are defined as centroids (geometrical 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. This result is based, first, on the proved properties of the problem optimal solution and, second, on the justified dynamic programming scheme.
AB - We consider a 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 clusters elements and their centers. The centers of one part of the clusters are given as an input, while the centers of the other part of the clusters are defined as centroids (geometrical 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. This result is based, first, on the proved properties of the problem optimal solution and, second, on the justified dynamic programming scheme.
KW - Euclidean space
KW - Minimum sum-of-squares clustering
KW - One-dimensional case
KW - Polynomial-time algorithm
KW - Strongly NP-hard problem
UR - http://www.scopus.com/inward/record.url?scp=85076160194&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-33394-2_16
DO - 10.1007/978-3-030-33394-2_16
M3 - Conference contribution
AN - SCOPUS:85076160194
SN - 9783030333935
T3 - Communications in Computer and Information Science
SP - 207
EP - 216
BT - Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers
A2 - Bykadorov, Igor
A2 - Strusevich, Vitaly
A2 - Tchemisova, Tatiana
PB - Springer International Publishing AG
Y2 - 8 July 2019 through 12 July 2019
ER -
ID: 22995093