Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Exact pseudopolynomial algorithm for one sequence partitioning problem. / Kel’manov, A. V.; Khamidullin, S. A.; Khandeev, V. I.
в: Automation and Remote Control, Том 78, № 1, 01.01.2017, стр. 67-74.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Exact pseudopolynomial algorithm for one sequence partitioning problem
AU - Kel’manov, A. V.
AU - Khamidullin, S. A.
AU - Khandeev, V. I.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - We consider a strongly NP-hard problem of partitioning a finite sequence of vectors in a Euclidean space into two clusters of given size with the criterion of minimizing the total sum of square distances from cluster elements to their centers. The center of the first cluster is subject to optimization, defined by the mean value of all vectors in this cluster. The center of the second cluster is fixed at the origin. The partition is subject to the following condition: the difference between indices of two subsequent vectors included in the first cluster is bounded from above and below by given constants. We propose an exact pseudopolynomial algorithm for the case of a problem where the dimension of the space is fixed, and components of input vectors are integer-valued.
AB - We consider a strongly NP-hard problem of partitioning a finite sequence of vectors in a Euclidean space into two clusters of given size with the criterion of minimizing the total sum of square distances from cluster elements to their centers. The center of the first cluster is subject to optimization, defined by the mean value of all vectors in this cluster. The center of the second cluster is fixed at the origin. The partition is subject to the following condition: the difference between indices of two subsequent vectors included in the first cluster is bounded from above and below by given constants. We propose an exact pseudopolynomial algorithm for the case of a problem where the dimension of the space is fixed, and components of input vectors are integer-valued.
KW - Euclidean space
KW - exact pseudopolynomial algorithm
KW - minimal sum of squared distances
KW - NP-hardness
KW - partition
KW - sequence of vectors
UR - http://www.scopus.com/inward/record.url?scp=85011807605&partnerID=8YFLogxK
U2 - 10.1134/S0005117917010052
DO - 10.1134/S0005117917010052
M3 - Article
AN - SCOPUS:85011807605
VL - 78
SP - 67
EP - 74
JO - Automation and Remote Control
JF - Automation and Remote Control
SN - 0005-1179
IS - 1
ER -
ID: 10312518