Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters. / Kel’manov, A. V.; Pyatkin, A. V.; Khandeev, V. I.
в: Doklady Mathematics, Том 99, № 1, 01.01.2019, стр. 52-56.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters
AU - Kel’manov, A. V.
AU - Pyatkin, A. V.
AU - Khandeev, V. I.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - Abstract: Two consimilar problems of searching for a family of disjoint subsets (clusters) in a finite set of points of Euclidean space are considered. In these problems, the task is to maximize the minimum cluster size so that the value of each intercluster quadratic variation does not exceed a given fraction (constant) of the total quadratic variation of the points of the input set with respect to its centroid. Both problems are proved to be NP-hard even on a line.
AB - Abstract: Two consimilar problems of searching for a family of disjoint subsets (clusters) in a finite set of points of Euclidean space are considered. In these problems, the task is to maximize the minimum cluster size so that the value of each intercluster quadratic variation does not exceed a given fraction (constant) of the total quadratic variation of the points of the input set with respect to its centroid. Both problems are proved to be NP-hard even on a line.
KW - ALGORITHM
KW - 2-CENTER
UR - http://www.scopus.com/inward/record.url?scp=85065864468&partnerID=8YFLogxK
U2 - 10.1134/S1064562419010162
DO - 10.1134/S1064562419010162
M3 - Article
AN - SCOPUS:85065864468
VL - 99
SP - 52
EP - 56
JO - Doklady Mathematics
JF - Doklady Mathematics
SN - 1064-5624
IS - 1
ER -
ID: 20050501