RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Института математики и механики УрО РАН // Архив

Тр. ИММ УрО РАН, 2019, том 25, номер 4, страницы 69–78 (Mi timm1671)

Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость

А. В. Кельмановab, А. В. Пяткинab, В. И. Хандеевab

a Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, г. Новосибирск
b Новосибирский национальный исследовательский государственный университет

Аннотация: В работе рассматривается задача кластеризации $N$-элементного множества точек в $d$-мерном евклидовом пространстве на два кластера. В этой задаче требуется найти $2$-разбиение, минимизирующее сумму (по обоим кластерам) внутрикластерных квадратичных разбросов точек относительно искомых центров. Центр одного кластера определяется как центроид (геометрический центр), а центр другого кластера является искомой точкой во входном множестве. Анализируется вариант задачи, в котором размеры (т. е. мощности) кластеров заданы, а их суммарный размер совпадает с размером входного множества. Доказано, что задача NP-трудна в сильном смысле. Установлено, что для нее не существует полностью полиномиальной аппроксимационной схемы, если P$\neq$ NP.

Ключевые слова: евклидово пространство, кластеризация, $2$-разбиение, квадратичный разброс, центр, центроид, медиана, сильная NP-трудность, несуществование полностью полиномиальной приближенной схемы, эффективная сводимость с сохранением точности.

УДК: 519.16+519.85

MSC: 68W25, 68Q25

Поступила в редакцию: 12.08.2019
Исправленный вариант: 10.09.2019
Принята в печать: 16.09.2019

DOI: 10.21538/0134-4889-2019-25-4-69-78


 Англоязычная версия: Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2021, 313, suppl. 1, S117–S124

Реферативные базы данных:


© МИАН, 2024