1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation

Standard

1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation. / Pyatkin, Artem V.

In: Yugoslav Journal of Operations Research, Vol. 33, No. 1, 2023, p. 59-69.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{0df4367517804c51b9f360f99f12b19a,

title = "1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation",

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

keywords = "2-approximation algorithm, 2-clustering, Euclidean space, mean, medoid, strong NP-hardness",

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

note = " The research was supported by the program of fundamental scientific researches of the SB RAS, project 0314-2019-0014 and by the Russian Foundation for Basic Research, project 19-01-00308.",

year = "2023",

doi = "10.2298/YJOR211018008P",

language = "English",

volume = "33",

pages = "59--69",

journal = "Yugoslav Journal of Operations Research",

issn = "0354-0243",

publisher = "University of Belgrade",

number = "1",

}

RIS

TY - JOUR

T1 - 1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation

AU - Pyatkin, Artem V.

N1 - The research was supported by the program of fundamental scientific researches of the SB RAS, project 0314-2019-0014 and by the Russian Foundation for Basic Research, project 19-01-00308.

PY - 2023

Y1 - 2023

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

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

KW - 2-approximation algorithm

KW - 2-clustering

KW - Euclidean space

KW - mean

KW - medoid

KW - strong NP-hardness

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85149693690&origin=inward&txGid=0ef835b184192143eff47bbc12190b22

UR - https://www.mendeley.com/catalogue/adffbbb5-d90a-3dda-9c53-da152eb16724/

U2 - 10.2298/YJOR211018008P

DO - 10.2298/YJOR211018008P

M3 - Article

VL - 33

SP - 59

EP - 69

JO - Yugoslav Journal of Operations Research

JF - Yugoslav Journal of Operations Research

SN - 0354-0243

IS - 1

ER -

ID: 56398412