Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes. / Pyatkin, Artem V.
Mathematical Optimization Theory and Operations Research: Recent Trends - 20th International Conference, MOTOR 2021, Revised Selected Papers. ред. / Alexander Strekalovsky; Yury Kochetov; Tatiana Gruzdeva; Andrei Orlov. Springer Science and Business Media Deutschland GmbH, 2021. стр. 248-256 (Communications in Computer and Information Science; Том 1476 CCIS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes
AU - Pyatkin, Artem V.
N1 - Publisher Copyright: © 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - We consider the following 2-clustering problem. Given n points in Euclidean space, partition it into two subsets (clusters) so that the sum of squared distances between the elements of the clusters and their centers would be minimum. The center of the first cluster coincides with its centroid (mean) while the center of the second cluster should be chosen from the set of the initial points (medoid). It is known that this problem is NP-hard if the cardinalities of the clusters are given as a part of the input. In this paper we prove that the peoblem remains NP-hard in the case of arbitrary clusters sizes.
AB - We consider the following 2-clustering problem. Given n points in Euclidean space, partition it into two subsets (clusters) so that the sum of squared distances between the elements of the clusters and their centers would be minimum. The center of the first cluster coincides with its centroid (mean) while the center of the second cluster should be chosen from the set of the initial points (medoid). It is known that this problem is NP-hard if the cardinalities of the clusters are given as a part of the input. In this paper we prove that the peoblem remains NP-hard in the case of arbitrary clusters sizes.
KW - 2-clustering
KW - Euclidean space
KW - Mean
KW - Medoid
KW - Strong NP-hardness
UR - http://www.scopus.com/inward/record.url?scp=85115847034&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-86433-0_17
DO - 10.1007/978-3-030-86433-0_17
M3 - Conference contribution
AN - SCOPUS:85115847034
SN - 9783030864323
T3 - Communications in Computer and Information Science
SP - 248
EP - 256
BT - Mathematical Optimization Theory and Operations Research
A2 - Strekalovsky, Alexander
A2 - Kochetov, Yury
A2 - Gruzdeva, Tatiana
A2 - Orlov, Andrei
PB - Springer Science and Business Media Deutschland GmbH
T2 - 20th International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2021
Y2 - 5 July 2021 through 10 July 2021
ER -
ID: 34339712