Research output: Contribution to journal › Article › peer-review
Complexity of Some Problems of Quadratic Partitioning of a Finite Set of Points in Euclidean Space into Balanced Clusters. / Kel’manov, A. V.; Pyatkin, A. V.; Khandeev, V. I.
In: Computational Mathematics and Mathematical Physics, Vol. 60, No. 1, 01.2020, p. 163-170.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Complexity of Some Problems of Quadratic Partitioning of a Finite Set of Points in Euclidean Space into Balanced Clusters
AU - Kel’manov, A. V.
AU - Pyatkin, A. V.
AU - Khandeev, V. I.
PY - 2020/1
Y1 - 2020/1
N2 - 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 the intracluster quadratic variance normalized by the cluster size in the first problem, the intracluster quadratic variance in the second problem, and the size-weighted intracluster variance in the third problem. The NP-completeness of all these problems is proved.
AB - 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 the intracluster quadratic variance normalized by the cluster size in the first problem, the intracluster quadratic variance in the second problem, and the size-weighted intracluster variance in the third problem. The NP-completeness of all these problems is proved.
KW - balanced partition
KW - Euclidean space
KW - NP-completeness
KW - quadratic variance
KW - size-weighted variance
KW - variance normalized by the cluster size
KW - SUM
UR - http://www.scopus.com/inward/record.url?scp=85082601642&partnerID=8YFLogxK
U2 - 10.1134/S096554251911006X
DO - 10.1134/S096554251911006X
M3 - Article
AN - SCOPUS:85082601642
VL - 60
SP - 163
EP - 170
JO - Computational Mathematics and Mathematical Physics
JF - Computational Mathematics and Mathematical Physics
SN - 0965-5425
IS - 1
ER -
ID: 23950041