Email this article NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters
- Authors: Kel’manov A.V.1,2, Pyatkin A.V.1,2, Khandeev V.I.1,2
-
Affiliations:
- Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
- Novosibirsk State University
- Issue: Vol 100, No 2 (2019)
- Pages: 416-419
- Section: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225709
- DOI: https://doi.org/10.1134/S1064562419050028
- ID: 225709
Cite item
Open Access
Access granted
Subscription Access
Abstract
We consider three related problems of partitioning an \(N\)-element set of points in \(d\)-dimensional Euclidean space into two clusters balancing the value of (1) the intracluster quadratic variance normalized by the cluster size in the first problem; (2) the intracluster quadratic variance in the second problem; and (3) the size-weighted intracluster quadratic variance in the third problem. The NP-completeness of all these problems is proved.
About the authors
A. V. Kel’manov
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Author for correspondence.
Email: kelm@math.nsc.ru
Russian Federation, Novosibirsk, 630090; Novosibirsk, 630090
A. V. Pyatkin
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Author for correspondence.
Email: artem@math.nsc.ru
Russian Federation, Novosibirsk, 630090; Novosibirsk, 630090
V. I. Khandeev
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Author for correspondence.
Email: khandeev@math.nsc.ru
Russian Federation, Novosibirsk, 630090; Novosibirsk, 630090
