1-Mean and 1-Medoid 2-Clustering Problem With Arbitrary Cluster Sizes: Complexity and Approximation

  • Artem V. Pyatkin Sobolev Institute of Mathematics, Russia, 630090, Novosibirsk, Koptyug Ave., 4 Novosibirsk State University, Russia, 630090, Novosibirsk, Pirogova Str., 2

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 problem remains NP-hard in the case of arbitrary clusters sizes and suggest a 2-approximation polynomial-time algorithm for this problem.

Published
May 8, 2022
How to Cite
PYATKIN, Artem V.. 1-Mean and 1-Medoid 2-Clustering Problem With Arbitrary Cluster Sizes: Complexity and Approximation. Yugoslav Journal of Operations Research, [S.l.], v. 33, n. 1, p. 59-69, may 2022. ISSN 2334-6043. Available at: <http://yujor.fon.bg.ac.rs/index.php/yujor/article/view/1040>. Date accessed: 28 mar. 2024. doi: http://dx.doi.org/10.2298/YJOR211018008P.
Section
Research Articles