Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
A Randomized Algorithm for a Sequence 2-Clustering Problem. / Kel'manov, A. V.; Khamidullin, S. A.; Khandeev, V. I.
в: Computational Mathematics and Mathematical Physics, Том 58, № 12, 01.01.2018, стр. 2078-2085.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - A Randomized Algorithm for a Sequence 2-Clustering Problem
AU - Kel'manov, A. V.
AU - Khamidullin, S. A.
AU - Khandeev, V. I.
PY - 2018/1/1
Y1 - 2018/1/1
N2 - We consider a strongly NP-hard problem of partitioning a finite Euclidean sequence into two clusters of given cardinalities minimizing the sum over both clusters of intracluster sums of squared distances from clusters elements to their centers. The center of one cluster is unknown and is defined as the mean value of all points in the cluster. The center of the other cluster is the origin. Additionally, the difference between the indices of two consequent points from the first cluster is bounded from below and above by some constants. A randomized algorithm that finds an approximation solution of the problem in polynomial time for given values of the relative error and failure probability and for an established parameter value is proposed. The conditions are established under which the algorithm is polynomial and asymptotically exact.
AB - We consider a strongly NP-hard problem of partitioning a finite Euclidean sequence into two clusters of given cardinalities minimizing the sum over both clusters of intracluster sums of squared distances from clusters elements to their centers. The center of one cluster is unknown and is defined as the mean value of all points in the cluster. The center of the other cluster is the origin. Additionally, the difference between the indices of two consequent points from the first cluster is bounded from below and above by some constants. A randomized algorithm that finds an approximation solution of the problem in polynomial time for given values of the relative error and failure probability and for an established parameter value is proposed. The conditions are established under which the algorithm is polynomial and asymptotically exact.
KW - partitioning
KW - sequence
KW - Euclidean space
KW - minimum sum-of-squared distances
KW - NP-hardness
KW - randomized algorithm
KW - asymptotic accuracy
KW - Asymptotic accuracy
KW - Partitioning
KW - Sequence
KW - Randomized algorithm
KW - Minimum sum-of-squared distances
UR - http://www.scopus.com/inward/record.url?scp=85057742799&partnerID=8YFLogxK
U2 - 10.1134/S0965542518120138
DO - 10.1134/S0965542518120138
M3 - Article
VL - 58
SP - 2078
EP - 2085
JO - Computational Mathematics and Mathematical Physics
JF - Computational Mathematics and Mathematical Physics
SN - 0965-5425
IS - 12
ER -
ID: 18631871