Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Randomized algorithms for some clustering problems. / Kel’manov, Alexander; Khandeev, Vladimir; Panasenko, Anna.
Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG, 2018. p. 109-119 (Communications in Computer and Information Science; Vol. 871).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Randomized algorithms for some clustering problems
AU - Kel’manov, Alexander
AU - Khandeev, Vladimir
AU - Panasenko, Anna
N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.
PY - 2018/1/1
Y1 - 2018/1/1
N2 - We consider two strongly NP-hard problems of clustering a finite set of points in Euclidean Space. Both problems have applications, in particular, in data analysis, data mining, pattern recognition, and machine learning. In the first problem, an input set is given and we need to find a cluster (i.e., a subset) of a given size which minimizes the sum of squared distances between the elements of this cluster and its centroid (the geometric center). Every point outside this cluster is considered as singleton cluster. In the second problem, we need to partition a finite set into two clusters minimizing the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first cluster is unknown and determined as the centroid, while the center of the second one is the origin. The weight factors for both intracluster sums are the given clusters sizes. In this paper, we present parameterized randomized algorithms for these problems. For given upper bounds of the relative error and failure probability, the parameter value is defined for which both our algorithms find approximate solutions in a polynomial time. This running time is linear on the space dimension and on the input set size. The conditions are found under which these algorithms are asymptotically exact and have the time complexity that is linear on the space dimension and quadratic on the size of the input set.
AB - We consider two strongly NP-hard problems of clustering a finite set of points in Euclidean Space. Both problems have applications, in particular, in data analysis, data mining, pattern recognition, and machine learning. In the first problem, an input set is given and we need to find a cluster (i.e., a subset) of a given size which minimizes the sum of squared distances between the elements of this cluster and its centroid (the geometric center). Every point outside this cluster is considered as singleton cluster. In the second problem, we need to partition a finite set into two clusters minimizing the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first cluster is unknown and determined as the centroid, while the center of the second one is the origin. The weight factors for both intracluster sums are the given clusters sizes. In this paper, we present parameterized randomized algorithms for these problems. For given upper bounds of the relative error and failure probability, the parameter value is defined for which both our algorithms find approximate solutions in a polynomial time. This running time is linear on the space dimension and on the input set size. The conditions are found under which these algorithms are asymptotically exact and have the time complexity that is linear on the space dimension and quadratic on the size of the input set.
KW - Approximation algorithm
KW - Asymptotic accuracy
KW - Clustering
KW - Euclidean space
KW - NP-hardness
KW - Randomized
UR - http://www.scopus.com/inward/record.url?scp=85049677271&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-93800-4_9
DO - 10.1007/978-3-319-93800-4_9
M3 - Conference contribution
AN - SCOPUS:85049677271
SN - 9783319937991
T3 - Communications in Computer and Information Science
SP - 109
EP - 119
BT - Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers
PB - Springer-Verlag GmbH and Co. KG
T2 - 7th International Conference on Optimization Problems and Their Applications, OPTA 2018
Y2 - 8 June 2018 through 14 June 2018
ER -
ID: 14464907