Том 27, номер 3, 2020 г., Стр. 88-108

УДК 519.8
Ильев В. П., Ильева С. Д., Моршинин А. В.
2-Приближенные алгоритмы для двух задач кластеризации на графах

Аннотация:
Изучаются вариант задачи $2$-кластеризации на графе и соответствующая задача с частичным обучением. В этих задачах для данного графа требуется найти ближайший $2$-кластерный граф, т. е. граф на том же множестве вершин, имеющий ровно $2$ непустые компоненты связности, каждая из которых является полным графом. Расстояние между графами равно числу их несовпадающих рёбер. Обе рассматриваемые задачи NP-трудны. В 2008 г. Коулман, Саундерсон и Вирт предложили полиномиальный $2$-приближённый алгоритм для аналогичной задачи, в которой число кластеров не превосходит $2$. К сожалению, метод доказательства гарантированной оценки точности алгоритма Коулмана, Саундерсона и Вирта неприменим для задачи $2$-кластеризации на графе, в которой число кластеров в точности равно $2$. Мы предлагаем полиномиальный $2$-приближённый алгоритм для задачи $2$-кластеризации на произвольном графе. В отличие от доказательства Коулмана, Саундерсона и Вирта, наше доказательство гарантированной оценки точности этого алгоритма не использует техники переключений. Кроме того, предложен аналогичный $2$-приближённый алгоритм для соответствующей задачи с частичным обучением.
Библиогр. 9.

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

DOI: 10.33048/daio.2020.27.680

Ильев Виктор Петрович ^1,2
Ильева Светлана Диадоровна ¹
Моршинин Александр Владимирович ²
1. Омский гос. университет им. Ф. М. Достоевского,
пр. Мира, 55-А, 644077 Омск, Россия
2. Омский филиал Института математики им. С. Л. Соболева,
ул. Певцова, 13, 644043 Омск, Россия
е-mail: iljev@mail.ru, morshinin.alexander@gmail.com

Статья поступила 10 января 2020 г.
После доработки — 6 мая 2020 г.
Принята к публикации 25 мая 2020 г.

Литература

[1] Bansal N., Blum A., Chawla S. Correlation clustering // Mach. Learn. 2004. Vol. 56, No. 1–3. P. 89–113.

[2] Coleman T., Saunderson J., Wirth A. A local-search 2-approximation for 2-correlation-clustering // Algorithms – ESA 2008. Proc. 16th Annu. Eur. Symp. (Karlsruhe, Germany, Sept. 15–17, 2008). Heidelberg: Springer, 2008. P. 308–319. (Lect. Notes Comput. Sci.; Vol. 5193).

[3] Shamir R., Sharan R., Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. Vol. 144, No. 1–2. P. 173–182.

[4] Zahn C. T. Approximating symmetric relations by equivalence relations // J. Soc. Ind. Appl. Math. 1964. Vol. 12, No. 4. P. 840–847.

[5] Ильев В. П., Фридман Г. Ш. К задаче аппроксимации графами с фиксированным числом компонент // Докл. АН СССР. 1982. Т. 264, № 3. С. 533–538.

[6] Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С. Вычислительная сложность задачи аппроксимации графов // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13, № 1. С. 3–11.

[7] Giotis I., Guruswami V. Correlation clustering with a fixed number of clusters // Theory Comput. 2006. Vol. 2, No. 1. P. 249–266.

[8] Chapelle O., Schölkopf B., Zein A. Semi-supervised learning. Cambridge, MA: MIT Press, 2006.

[9] Bair E. Semi-supervised clustering methods // Wiley Interdisciplinary Reviews: Computational Statistics. 2013. Vol. 5, No. 5. P. 349–361.