@inproceedings{92fca3d21d1249439c680d5b0c910b05,

title = "A PTAS for one cardinality-weighted 2-clustering problem",

abstract = "We consider one strongly NP-hard problem of clustering a finite set of points in Euclidean space. In this problem, we need to partition a finite set of points into two clusters minimizing the sum over both clusters of the weighted intracluster sums. Each of these sums is the sum of squared distances between the elements of the cluster and their center. The center of the one cluster is unknown and determined as the centroid, while the center of the other one is fixed at the origin. The weight factors for both intracluster sums are the given sizes of the clusters. In this paper, we present an approximation algorithm for the problem and prove that it is a polynomial-time approximation scheme (PTAS).",

keywords = "Approximation algorithm, Euclidean space, NP-hardness, PTAS, Quadratic variation, Weighted 2-clustering, APPROXIMATION SCHEME, ALGORITHM",

author = "Anna Panasenko",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-22629-9_41",

language = "English",

isbn = "9783030226282",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag GmbH and Co. KG",

pages = "581--592",

editor = "Michael Khachay and Panos Pardalos and Yury Kochetov",

booktitle = "Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings",

address = "Germany",

note = "18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 ; Conference date: 08-07-2019 Through 12-07-2019",

}