Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
On the Complexity of SomeMax-Min Clustering Problems. / Kel'manov, A. V.; Pyatkin, A. V.; Khandeev, V. I.
в: Proceedings of the Steklov Institute of Mathematics, Том 309, № SUPPL 1, 08.2020, стр. S65-S73.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - On the Complexity of SomeMax-Min Clustering Problems
AU - Kel'manov, A. V.
AU - Pyatkin, A. V.
AU - Khandeev, V. I.
N1 - Funding Information: This work was supported by the Russian Science Foundation (project no. 16-11-10041). Publisher Copyright: © Pleiades Publishing, Ltd., 2020. c.
PY - 2020/8
Y1 - 2020/8
N2 - Two similar problems of searching for a family of disjoint subsets (clusters) in a finite set of points in Euclidean space are considered. In these problems, the size of the smallest cluster should be maximized so that in each cluster the intracluster quadratic variation of the points with respect to the center of the cluster would not exceed a given (constant) fraction of the total quadratic variation of the points of the input set with respect to its centroid. In the first problem, the centers of intracluster variations are arbitrary points of the space given at the input. In the second problem, the centers of the intracluster variation are unknown (to be found) but must lie in the input set. Both problems are proved to be NP-hard even on the real line both in the general case when the number of the clusters is a part of the input and in the parametric case when the number of the clusters is fixed.
AB - Two similar problems of searching for a family of disjoint subsets (clusters) in a finite set of points in Euclidean space are considered. In these problems, the size of the smallest cluster should be maximized so that in each cluster the intracluster quadratic variation of the points with respect to the center of the cluster would not exceed a given (constant) fraction of the total quadratic variation of the points of the input set with respect to its centroid. In the first problem, the centers of intracluster variations are arbitrary points of the space given at the input. In the second problem, the centers of the intracluster variation are unknown (to be found) but must lie in the input set. Both problems are proved to be NP-hard even on the real line both in the general case when the number of the clusters is a part of the input and in the parametric case when the number of the clusters is fixed.
KW - Euclidean space
KW - clustering
KW - max-min problem
KW - quadratic variation
KW - NP-hardness
KW - NP-HARDNESS
KW - max–min problem
UR - http://www.scopus.com/inward/record.url?scp=85140577971&partnerID=8YFLogxK
U2 - 10.1134/S0081543820040082
DO - 10.1134/S0081543820040082
M3 - Article
VL - 309
SP - S65-S73
JO - Proceedings of the Steklov Institute of Mathematics
JF - Proceedings of the Steklov Institute of Mathematics
SN - 0081-5438
IS - SUPPL 1
ER -
ID: 26085181