1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation Full article
| Journal |
Yugoslav Journal of Operations Research
ISSN: 0354-0243 , E-ISSN: 2334-6043 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2023, Volume: 33, Number: 1, Pages: 59-69 Pages count : 11 DOI: 10.2298/yjor211018008p | ||||
| Tags | Euclidean space, mean, medoid, 2-clustering, 2-approximation algorithm, strong NP-hardness. | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | 0314-2019-0014 |
| 2 | Russian Foundation for Basic Research | 19-01-00308 |
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 clust/
Cite:
Pyatkin A.V.
1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation
Yugoslav Journal of Operations Research. 2023. V.33. N1. P.59-69. DOI: 10.2298/yjor211018008p Scopus РИНЦ OpenAlex
1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation
Yugoslav Journal of Operations Research. 2023. V.33. N1. P.59-69. DOI: 10.2298/yjor211018008p Scopus РИНЦ OpenAlex
Dates:
| Submitted: | Oct 14, 2021 |
| Accepted: | Apr 14, 2022 |
| Published online: | Sep 27, 2022 |
| Published print: | Feb 15, 2023 |
Identifiers:
| Scopus: | 2-s2.0-85149693690 |
| Elibrary: | 60074979 |
| OpenAlex: | W4285269600 |