Research output: Contribution to journal › Article › peer-review
Randomized Algorithms for Some Hard-to-Solve Problems of Clustering a Finite Set of Points in Euclidean Space. / Kel’manov, A. V.; Panasenko, A. V.; Khandeev, V. I.
In: Computational Mathematics and Mathematical Physics, Vol. 59, No. 5, 01.05.2019, p. 842-850.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Randomized Algorithms for Some Hard-to-Solve Problems of Clustering a Finite Set of Points in Euclidean Space
AU - Kel’manov, A. V.
AU - Panasenko, A. V.
AU - Khandeev, V. I.
PY - 2019/5/1
Y1 - 2019/5/1
N2 - Two strongly NP-hard problems of clustering a finite set of points in Euclidean space are considered. In the first problem, given an input set, we need to find a cluster (i.e., a subset) of given size that minimizes the sum of the squared distances between the elements of this cluster and its centroid (geometric center). Every point outside this cluster is considered a singleton cluster. In the second problem, we need to partition a finite set into two clusters minimizing the sum, over both clusters, of weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The center of one of the clusters is unknown and is determined as its centroid, while the center of the other cluster is set at some point of space (without loss of generality, at the origin). The weighting factors for both intracluster sums are the given cluster sizes. Parameterized randomized algorithms are presented for both problems. For given upper bounds on the relative error and the failure probability, the parameter value is defined for which both algorithms find approximation solutions in polynomial time. This running time is linear in the space dimension and the size of the input set. The conditions are found under which the algorithms are asymptotically exact and their time complexity is linear in the space dimension and quadratic in the input set size.
AB - Two strongly NP-hard problems of clustering a finite set of points in Euclidean space are considered. In the first problem, given an input set, we need to find a cluster (i.e., a subset) of given size that minimizes the sum of the squared distances between the elements of this cluster and its centroid (geometric center). Every point outside this cluster is considered a singleton cluster. In the second problem, we need to partition a finite set into two clusters minimizing the sum, over both clusters, of weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The center of one of the clusters is unknown and is determined as its centroid, while the center of the other cluster is set at some point of space (without loss of generality, at the origin). The weighting factors for both intracluster sums are the given cluster sizes. Parameterized randomized algorithms are presented for both problems. For given upper bounds on the relative error and the failure probability, the parameter value is defined for which both algorithms find approximation solutions in polynomial time. This running time is linear in the space dimension and the size of the input set. The conditions are found under which the algorithms are asymptotically exact and their time complexity is linear in the space dimension and quadratic in the input set size.
KW - approximation algorithm
KW - Euclidean space
KW - minimum sum-of-squared distances
KW - NP-hardness
KW - partitioning
KW - sequence
UR - http://www.scopus.com/inward/record.url?scp=85067476464&partnerID=8YFLogxK
U2 - 10.1134/S0965542519050099
DO - 10.1134/S0965542519050099
M3 - Article
AN - SCOPUS:85067476464
VL - 59
SP - 842
EP - 850
JO - Computational Mathematics and Mathematical Physics
JF - Computational Mathematics and Mathematical Physics
SN - 0965-5425
IS - 5
ER -
ID: 20643006