Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points. / Kel’manov, A. V.; Pyatkin, A. V.
в: Computational Mathematics and Mathematical Physics, Том 58, № 5, 01.05.2018, стр. 822-826.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points
AU - Kel’manov, A. V.
AU - Pyatkin, A. V.
N1 - Publisher Copyright: © 2018, Pleiades Publishing, Ltd.
PY - 2018/5/1
Y1 - 2018/5/1
N2 - Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).
AB - Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).
KW - Euclidean space
KW - norm of sum
KW - NP-hardness
KW - partitioning
UR - http://www.scopus.com/inward/record.url?scp=85048616703&partnerID=8YFLogxK
U2 - 10.1134/S0965542518050123
DO - 10.1134/S0965542518050123
M3 - Article
AN - SCOPUS:85048616703
VL - 58
SP - 822
EP - 826
JO - Computational Mathematics and Mathematical Physics
JF - Computational Mathematics and Mathematical Physics
SN - 0965-5425
IS - 5
ER -
ID: 14048528