|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
О сложности некоторых максиминных задач кластеризации
А. В. Кельмановab, А. В. Пяткинab, В. И. Хандеевab a Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, г. Новосибирск
b Новосибирский национальный исследовательский государственный университет
Аннотация:
Рассматриваются две родственные задачи поиска семейства непересекающихся подмножеств (кластеров) в конечном множестве точек евклидова пространства. В этих задачах требуется максимизировать размер минимального по мощности кластера так, чтобы в каждом кластере суммарный внутрикластерный квадратичный разброс точек относительно центра кластера не превышал заданной доли (константы) от суммарного квадратичного разброса точек во входном множестве относительно его геометрического центра. В первой задаче центры внутрикластерных разбросов - произвольные, но заданные на входе точки пространства. Во второй задаче центры внутрикластерного разброса неизвестны (являются искомыми точками), но принадлежат входному множеству. Доказано, что обе задачи NP-трудны даже на числовой прямой как в общем случае, когда число кластеров является частью входа, так и в параметрическом случае, когда число кластеров фиксировано.
Ключевые слова:
евклидово пространство, кластеризация, максиминная задача, квадратичный разброс, NP-трудность.
Поступила в редакцию: 30.07.2018 Исправленный вариант: 08.10.2018 Принята в печать: 12.11.2018
Образец цитирования:
А. В. Кельманов, А. В. Пяткин, В. И. Хандеев, “О сложности некоторых максиминных задач кластеризации”, Тр. ИММ УрО РАН, 24, № 4, 2018, 189–198; Proc. Steklov Inst. Math. (Suppl.), 309, suppl. 1 (2020), S65–S73
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1585 https://www.mathnet.ru/rus/timm/v24/i4/p189
|
Статистика просмотров: |
Страница аннотации: | 189 | PDF полного текста: | 50 | Список литературы: | 34 | Первая страница: | 2 |
|