Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Randomized algorithms for some sequence clustering problems. / Khamidullin, Sergey; Khandeev, Vladimir; Panasenko, Anna.
Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers. ред. / Ilias S. Kotsireas; Panos M. Pardalos. Springer Gabler, 2020. стр. 96-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12096 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Randomized algorithms for some sequence clustering problems
AU - Khamidullin, Sergey
AU - Khandeev, Vladimir
AU - Panasenko, Anna
PY - 2020/6/1
Y1 - 2020/6/1
N2 - We consider two problems of clustering a finite sequence of points in Euclidean space. In the first problem, we need to find a cluster minimizing intracluster sum of squared distances from cluster elements to its centroid. In the second problem, we need to partition a sequence into two clusters minimizing cardinality-weighted intracluster sums of squared distances from clusters elements to their centers; the center of the first cluster is its centroid, while the center of the second one is the origin. Moreover, in the first problem, the difference between any two subsequent indices of cluster elements is bounded above and below by some constants. In the second problem, the same constraint is imposed on the cluster with unknown centroid. We present randomized algorithms for both problems and find the conditions under which these algorithms are polynomial and asymptotically exact.
AB - We consider two problems of clustering a finite sequence of points in Euclidean space. In the first problem, we need to find a cluster minimizing intracluster sum of squared distances from cluster elements to its centroid. In the second problem, we need to partition a sequence into two clusters minimizing cardinality-weighted intracluster sums of squared distances from clusters elements to their centers; the center of the first cluster is its centroid, while the center of the second one is the origin. Moreover, in the first problem, the difference between any two subsequent indices of cluster elements is bounded above and below by some constants. In the second problem, the same constraint is imposed on the cluster with unknown centroid. We present randomized algorithms for both problems and find the conditions under which these algorithms are polynomial and asymptotically exact.
KW - Asymptotic accuracy
KW - Clustering
KW - Euclidean space
KW - Minimum sum-of-squares
KW - NP-hard problem
KW - Randomized algorithm
UR - http://www.scopus.com/inward/record.url?scp=85089213553&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-53552-0_11
DO - 10.1007/978-3-030-53552-0_11
M3 - Conference contribution
AN - SCOPUS:85089213553
SN - 9783030535513
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 96
EP - 101
BT - Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers
A2 - Kotsireas, Ilias S.
A2 - Pardalos, Panos M.
PB - Springer Gabler
T2 - 14th International Conference on Learning and Intelligent Optimization, LION 2020
Y2 - 24 May 2020 through 28 May 2020
ER -
ID: 24956058