|
Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость
А. В. Кельмановab, А. В. Пяткинab, В. И. Хандеевab a Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, г. Новосибирск
b Новосибирский национальный исследовательский государственный университет
Аннотация:
В работе рассматривается задача кластеризации $N$-элементного множества
точек в $d$-мерном евклидовом пространстве на два кластера. В этой задаче требуется найти
$2$-разбиение,
минимизирующее сумму (по обоим кластерам) внутрикластерных квадратичных разбросов точек относительно
искомых центров. Центр одного кластера определяется как
центроид (геометрический центр), а центр другого кластера
является искомой точкой во входном множестве. Анализируется вариант
задачи, в котором размеры (т. е. мощности) кластеров заданы, а их суммарный
размер совпадает с размером входного множества. Доказано,
что задача NP-трудна в сильном смысле. Установлено, что для нее не существует
полностью полиномиальной аппроксимационной схемы, если P$\neq$ NP.
Ключевые слова:
евклидово пространство, кластеризация, $2$-разбиение, квадратичный разброс, центр, центроид, медиана, сильная NP-трудность, несуществование полностью полиномиальной приближенной схемы, эффективная сводимость с сохранением точности.
Поступила в редакцию: 12.08.2019 Исправленный вариант: 10.09.2019 Принята в печать: 16.09.2019
Образец цитирования:
А. В. Кельманов, А. В. Пяткин, В. И. Хандеев, “Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость”, Тр. ИММ УрО РАН, 25, № 4, 2019, 69–78; Proc. Steklov Inst. Math. (Suppl.), 313, suppl. 1 (2021), S117–S124
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1671 https://www.mathnet.ru/rus/timm/v25/i4/p69
|
Статистика просмотров: |
Страница аннотации: | 158 | PDF полного текста: | 40 | Список литературы: | 26 | Первая страница: | 1 |
|