On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters

A. V. Kel’manov, A. V. Pyatkin, V. I. Khandeev

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)52-56
Число страниц5
ЖурналDoklady Mathematics
Том99
Номер выпуска1
DOI
СостояниеОпубликовано - 1 янв 2019

Fingerprint Подробные сведения о темах исследования «On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать