Geodesic
1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: complexity and approximation
Yugoslav journal of operations research, Tome 33 (2023) no. 1, p. 59 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

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.
Classification : 68W25, 90C27
Keywords: Euclidean space, mean, medoid, 2-clustering, 2-approximation algorithm, strong NP-hardness 
@article{YJOR_2023_33_1_a3,
     author = {Artem V Pyatkin},
     title = {1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: complexity and approximation},
     journal = {Yugoslav journal of operations research},
     pages = {59 },
     year = {2023},
     volume = {33},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2023_33_1_a3/}
}
TY  - JOUR
AU  - Artem V Pyatkin
TI  - 1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: complexity and approximation
JO  - Yugoslav journal of operations research
PY  - 2023
SP  - 59 
VL  - 33
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/YJOR_2023_33_1_a3/
LA  - en
ID  - YJOR_2023_33_1_a3
ER  - 
%0 Journal Article
%A Artem V Pyatkin
%T 1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: complexity and approximation
%J Yugoslav journal of operations research
%D 2023
%P 59 
%V 33
%N 1
%U http://geodesic.mathdoc.fr/item/YJOR_2023_33_1_a3/
%G en
%F YJOR_2023_33_1_a3
Artem V Pyatkin. 1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: complexity and approximation. Yugoslav journal of operations research, Tome 33 (2023) no. 1, p. 59 . http://geodesic.mathdoc.fr/item/YJOR_2023_33_1_a3/