RUS  ENG
Полная версия
ЖУРНАЛЫ // Журнал вычислительной математики и математической физики // Архив

Ж. вычисл. матем. и матем. физ., 2019, том 59, номер 9, страницы 1617–1625 (Mi zvmmf10959)

Эта публикация цитируется в 1 статье

Полиномиальная разрешимость одномерного случая одной NP-трудной задачи кластеризации

А. В. Кельмановab, В. И. Хандеевab

a 630090 Новосибирск, пр-т акад. Коптюга, 4, Ин-т матем. им. С.Л. Соболева, Россия
b 630090 Новосибирск, ул. Пирогова, 2, Новосибирский гос. ун-т, Россия

Аннотация: Рассматривается задача разбиения конечного множества точек евклидова пространства на кластеры по критерию минимума суммы по всем кластерам внутрикластерных сумм квадратов расстояний между элементами кластеров и их центрами. Центры одной части кластеров заданы на входе задачи, а центры другой части кластеров неизвестны и определяются как центроиды (геометрические центры). Известно, что в общем случае эта задача NP-трудна в сильном смысле. В работе конструктивно доказано, что одномерный случай задачи разрешим за полиномиальное время. Библ. 20.

Ключевые слова: евклидово пространство, кластеризация, разбиение, минимум суммы квадратов расстояний, NP-трудная в сильном смысле задача, одномерный случай, полиномиальная разрешимость.

УДК: 519.72

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

DOI: 10.1134/S0044466919090114


 Англоязычная версия: Computational Mathematics and Mathematical Physics, 2019, 59:9, 1553–1561

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


© МИАН, 2024