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

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

Журнал

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

Вых. Данные

Год: 2024, Том: 31, Номер: 2, Страницы: 113-119 Страниц : 7 DOI: 10.33048/daio.2024.31.787

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

кластер, центроид, разброс, NP-трудность.

Авторы

Пяткин А.В. ¹

Организации

1	Институт математики им. С. Л. Соболева

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

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

FWNF-2022-0019

Рассматривается задача выбора в данном множестве евклидовых векторов заданного числа кластеров с ограничением на максимальный разброс каждого кластера так, чтобы размер минимального из этих кластеров был максимальным. Под разбросом понимается сумма квадратов расстояний от элементов кластера до его центроида. Доказана NP-трудность этой задачи в случае, когда размерность пространства является частью входа.

Пяткин А.В.
О сложности задачи выбора кластеров большого размера
Дискретный анализ и исследование операций. 2024. Т.31. №2. С.113-119. DOI: 10.33048/daio.2024.31.787 РИНЦ

Pyatkin A.V.
On the Complexity of the Problem of Choice of Large Clusters
Journal of Applied and Industrial Mathematics. 2024. V.18. N2. P.312-315. DOI: 10.1134/S1990478924020121 Scopus РИНЦ OpenAlex

Поступила в редакцию:	8 нояб. 2023 г.
Принята к публикации:	22 дек. 2023 г.
Опубликована в печати:	30 мая 2024 г.
Опубликована online:	30 мая 2024 г.

РИНЦ:

68484583

Пока нет цитирований