Exact pseudopolynomial algorithms for a balanced 2-clustering problem
- Authors: Kel’manov A.V.1,2, Motkova A.V.2
-
Affiliations:
- Sobolev Institute of Mathematics
- Novosibirsk State University
- Issue: Vol 10, No 3 (2016)
- Pages: 349-355
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212408
- DOI: https://doi.org/10.1134/S1990478916030054
- ID: 212408
Cite item
Abstract
We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the sizes of the clusters. The center of one cluster is given as input, while the center of the other cluster is unknown and determined as the average value over all points in the cluster (as the geometric center). Two variants of the problems are analyzed in which the cluster sizes are either given or unknown. We present and prove some exact pseudopolynomial algorithms in the case of integer components of the input points and fixed space dimension.
About the authors
A. V. Kel’manov
Sobolev Institute of Mathematics; Novosibirsk State University
Author for correspondence.
Email: kelm@math.nsc.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090
A. V. Motkova
Novosibirsk State University
Email: kelm@math.nsc.ru
Russian Federation, ul. Pirogova 2, Novosibirsk, 630090