О сложности двух задач поиска кластеров с большой мощностью | Sciact - Система учета научной деятельности ИМ СО РАН

О сложности двух задач поиска кластеров с большой мощностью Научная публикация

Журнал

Дискретный анализ и исследование операций
ISSN: 1560-7542

Вых. Данные

Год: 2025, Том: 32, Номер: 4, Страницы: 172–190 Страниц : 20 DOI: 10.33048/daio.2025.32.834

Ключевые слова

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

Авторы

Нещадим С.М. ¹ , Хандеев В.И. ²

Организации

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

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0015

В работе рассматриваются задачи поиска в конечном множестве точек евклидова пространства непересекающихся подмножеств. В одной из задач мощность каждого из подмножеств должна быть не меньше заданного числа. В другой задаче мощность всех подмножеств должна быть одинакова, и в объединении они должны совпадать со всем исходным множеством. В обеих задачах дополнительно требуется, чтобы для каждого подмножества сумма квадратов расстояний до центроида не превосходила заданной величины. Доказано, что задачи NP-полны в сильном смысле в случае, когда число кластеров равно двум, а размерность пространства является частью входа задачи. Кроме того, доказано, что задачи NP-полны в одномерном случае для любого фиксированного числа кластеров.

Нещадим С.М. , Хандеев В.И.
О сложности двух задач поиска кластеров с большой мощностью
Дискретный анализ и исследование операций. 2025. Т.32. №4. С.172–190. DOI: 10.33048/daio.2025.32.834

Поступила в редакцию:	5 мая 2025 г.
Принята к публикации:	22 сент. 2025 г.
Опубликована в печати:	4 июн. 2026 г.
Опубликована online:	4 июн. 2026 г.

Нет идентификаторов