@inproceedings{c8c90d517fc04f3f82b016dd3af8bbe8,

title = "NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes",

abstract = "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.",

keywords = "2-clustering, Euclidean space, Mean, Medoid, Strong NP-hardness",

author = "Pyatkin, {Artem V.}",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 20th International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2021 ; Conference date: 05-07-2021 Through 10-07-2021",

year = "2021",

doi = "10.1007/978-3-030-86433-0_17",

language = "English",

isbn = "9783030864323",

series = "Communications in Computer and Information Science",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "248--256",

editor = "Alexander Strekalovsky and Yury Kochetov and Tatiana Gruzdeva and Andrei Orlov",

booktitle = "Mathematical Optimization Theory and Operations Research",

address = "Germany",

}