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

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

Журнал

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

Вых. Данные

Год: 2024, Том: 31, Номер: 4, Страницы: 40–57 Страниц : 16 DOI: 10.33048/daio.2024.31.802

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

граф, кластеризация, NP-трудная задача, приближённый алгоритм, гарантированная оценка точности.

Авторы

Ильев В.П. ¹ , Ильева С.Д. ³ , Кононов А.В. ²

Организации

1	Институт математики им. С. Л. Соболева
2	Институт математики им. С. Л. Соболева
3	Омский гос. университет им. Ф. М. Достоевского

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

1	Институт математики им. С.Л. Соболева СО РАН	FWNF-2022-0019
2	Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН».	FWNF-2022-0020

В задачах кластеризации на графах требуется разбить множество вершин заданного графа на попарно непересекающиеся подмножества (называемые кластерами) так, чтобы минимизировать число рёбер между кластерами и число отсутствующих рёбер внутри кластеров. Мы рассматриваем вариант задачи, в котором размеры кластеров ограничены сверху натуральным числом s. Задача NP-трудна для любого фиксированного s 3. Для этого варианта задачи предложены полиномиальные приближённые алгоритмы с гарантированными оценками точности, равными 5/3 в случае s = 3 и 2 в случае s = 4. Доказано также, что при s = 3 задача APX-трудна. Ил. 5, библиогр. 20.

Ильев В.П. , Ильева С.Д. , Кононов А.В.
Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.40–57. DOI: 10.33048/daio.2024.31.802

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

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

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