Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
- Authors: Dolgushev A.V.1, Kel’manov A.V.1,2, Shenmaier V.V.2
-
Affiliations:
- Novosibirsk State University
- Sobolev Institute of Mathematics
- Issue: Vol 295, No Suppl 1 (2016)
- Pages: 47-56
- Section: Article
- URL: https://journals.rcsi.science/0081-5438/article/view/174035
- DOI: https://doi.org/10.1134/S0081543816090066
- ID: 174035
Cite item
Abstract
We consider the strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given cardinalities under the minimum criterion for the sum over the clusters of the intracluster sums of squared distances from elements of the cluster to its center. It is assumed that the center of one of the clusters is given (without loss of generality, at the origin). The center of the second cluster is unknown and is defined as the mean value over all elements in this cluster. A polynomial-time approximation scheme (PTAS) is provided.
Keywords
About the authors
A. V. Dolgushev
Novosibirsk State University
Author for correspondence.
Email: dolgushev@math.nsc.ru
Russian Federation, Novosibirsk, 630090
A. V. Kel’manov
Novosibirsk State University; Sobolev Institute of Mathematics
Email: dolgushev@math.nsc.ru
Russian Federation, Novosibirsk, 630090; Novosibirsk, 630090
V. V. Shenmaier
Sobolev Institute of Mathematics
Email: dolgushev@math.nsc.ru
Russian Federation, Novosibirsk, 630090
Supplementary files
