Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера Full article
| Journal |
Дискретный анализ и исследование операций
ISSN: 1560-7542 |
||||||
|---|---|---|---|---|---|---|---|
| Output data | Year: 2024, Volume: 31, Number: 4, Pages: 40–57 Pages count : 16 DOI: 10.33048/daio.2024.31.802 | ||||||
| Tags | граф, кластеризация, NP-трудная задача, приближённый алгоритм, гарантированная оценка точности. | ||||||
| Authors |
|
||||||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
| 2 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
Abstract:
В задачах кластеризации на графах требуется разбить множество вершин заданного графа на попарно непересекающиеся подмножества (называемые кластерами) так, чтобы минимизировать число рёбер между кластерами и число отсутствующих рёбер внутри кластеров. Мы рассматриваем вариант задачи, в котором размеры кластеров ограничены сверху натуральным числом s. Задача NP-трудна для любого фиксированного s 3. Для этого варианта задачи предложены полиномиальные приближённые алгоритмы с гарантированными оценками точности, равными 5/3 в случае s = 3 и 2 в случае s = 4. Доказано также, что при s = 3 задача APX-трудна. Ил. 5, библиогр. 20.
Cite:
Ильев В.П.
, Ильева С.Д.
, Кононов А.В.
Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.40–57. DOI: 10.33048/daio.2024.31.802
Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.40–57. DOI: 10.33048/daio.2024.31.802
Dates:
| Submitted: | May 17, 2024 |
| Accepted: | Jun 24, 2024 |
| Published print: | Dec 30, 2024 |
| Published online: | Dec 30, 2024 |
Identifiers:
No identifiers
Citing:
Пока нет цитирований