Отправить статью по E-mail On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters
- Авторы: Kel’manov A.V.1,2, Pyatkin A.V.1,2, Khandeev V.I.1,2
-
Учреждения:
- Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
- Novosibirsk State University
- Выпуск: Том 99, № 1 (2019)
- Страницы: 52-56
- Раздел: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225620
- DOI: https://doi.org/10.1134/S1064562419010162
- ID: 225620
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
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.
Об авторах
A. Kel’manov
Sobolev Institute of Mathematics, Siberian Branch,Russian Academy of Sciences; Novosibirsk State University
Автор, ответственный за переписку.
Email: kelm@math.nsc.ru
Россия, Novosibirsk, 630090; Novosibirsk, 630090
A. Pyatkin
Sobolev Institute of Mathematics, Siberian Branch,Russian Academy of Sciences; Novosibirsk State University
Автор, ответственный за переписку.
Email: artem@math.nsc.ru
Россия, Novosibirsk, 630090; Novosibirsk, 630090
V. Khandeev
Sobolev Institute of Mathematics, Siberian Branch,Russian Academy of Sciences; Novosibirsk State University
Автор, ответственный за переписку.
Email: khandeev@math.nsc.ru
Россия, Novosibirsk, 630090; Novosibirsk, 630090
Дополнительные файлы
