Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
On the Complexity of Some Quadratic Euclidean Partition Problems into Balanced Clusters. / Kel’manov, Alexander; Khandeev, Vladimir; Pyatkin, Artem.
Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. ed. / Milojica Jaćimović; Michael Khachay; Vlasta Malkova; Mikhail Posypkin. Springer Gabler, 2020. p. 127-136 (Communications in Computer and Information Science; Vol. 1145 CCIS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - On the Complexity of Some Quadratic Euclidean Partition Problems into Balanced Clusters
AU - Kel’manov, Alexander
AU - Khandeev, Vladimir
AU - Pyatkin, Artem
N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - We consider three problems of partitioning a finite set of N points in the d-dimensional Euclidean space into two clusters balancing the value of (1) the normalized by a cluster size sum of squared deviations from the mean, (2) the sum of squared deviations from the mean, and (3) the size-weighted sum of squared deviations from the mean. We have proved the NP-completeness of all these problems.
AB - We consider three problems of partitioning a finite set of N points in the d-dimensional Euclidean space into two clusters balancing the value of (1) the normalized by a cluster size sum of squared deviations from the mean, (2) the sum of squared deviations from the mean, and (3) the size-weighted sum of squared deviations from the mean. We have proved the NP-completeness of all these problems.
KW - Balanced partition
KW - Euclidean space
KW - Normalized by the cluster size
KW - NP-completeness
KW - Quadratic variance
KW - Sized-weighted
UR - http://www.scopus.com/inward/record.url?scp=85078452712&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-38603-0_10
DO - 10.1007/978-3-030-38603-0_10
M3 - Conference contribution
AN - SCOPUS:85078452712
SN - 9783030386023
T3 - Communications in Computer and Information Science
SP - 127
EP - 136
BT - Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers
A2 - Jaćimović, Milojica
A2 - Khachay, Michael
A2 - Malkova, Vlasta
A2 - Posypkin, Mikhail
PB - Springer Gabler
T2 - 10th International Conference on Optimization and Applications, OPTIMA 2019
Y2 - 30 September 2019 through 4 October 2019
ER -
ID: 23265235