Research output: Contribution to journal › Article › peer-review
Polynomial-Time Approximation Algorithm for the Problem of Cardinality-Weighted Variance-Based 2-Clustering with a Given Center. / Kel’manov, A. V.; Motkova, A. V.
In: Computational Mathematics and Mathematical Physics, Vol. 58, No. 1, 01.01.2018, p. 130-136.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Polynomial-Time Approximation Algorithm for the Problem of Cardinality-Weighted Variance-Based 2-Clustering with a Given Center
AU - Kel’manov, A. V.
AU - Motkova, A. V.
PY - 2018/1/1
Y1 - 2018/1/1
N2 - A strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters is considered. The solution criterion is the minimum of the sum (over both clusters) of weighted sums of squared distances from the elements of each cluster to its geometric center. The weights of the sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other is unknown and is determined as the point of space equal to the mean of the cluster elements. A version of the problem is analyzed in which the cardinalities of the clusters are given as input. A polynomial-time 2-approximation algorithm for solving the problem is constructed.
AB - A strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters is considered. The solution criterion is the minimum of the sum (over both clusters) of weighted sums of squared distances from the elements of each cluster to its geometric center. The weights of the sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other is unknown and is determined as the point of space equal to the mean of the cluster elements. A version of the problem is analyzed in which the cardinalities of the clusters are given as input. A polynomial-time 2-approximation algorithm for solving the problem is constructed.
KW - Euclidean space
KW - NP-hardness
KW - polynomial-time 2-approximation algorithm
KW - weighted 2-clustering
UR - http://www.scopus.com/inward/record.url?scp=85042701688&partnerID=8YFLogxK
U2 - 10.1134/S0965542518010074
DO - 10.1134/S0965542518010074
M3 - Article
AN - SCOPUS:85042701688
VL - 58
SP - 130
EP - 136
JO - Computational Mathematics and Mathematical Physics
JF - Computational Mathematics and Mathematical Physics
SN - 0965-5425
IS - 1
ER -
ID: 10496999