Том 23, номер 3, 2016 г., Cтр. 5–20

УДК 519.8
Ильев В. П., Ильева С. Д., Навроцкая А. А.
О задаче кластеризации графа с ограничением на размеры кластеров

Аннотация:
Изучается версия задачи кластеризации графа (известной также как задача аппроксимации графа), в которой размеры кластеров ограничены сверху заданным числом $p$. Для этой задачи предложен новый приближённый алгоритм с достижимой гарантированной оценкой точности. Тем самым показано, что задача кластеризации графа с ограничением на размеры кластеров принадлежит классу $APX$ для любого фиксированного $p$.
Ил. 2, библиогр. 20.

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

DOI: 10.17377/daio.2016.23.521

Ильев Виктор Петрович ^1,2
Ильева Светлана Диадоровна ²
Навроцкая Анна Александровна ^1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Омский гос. университет им. Ф. М. Достоевского,
пр. Мира, 55-А, 644077 Омск, Россия
е-mail: iljev@mail.ru, nawrocki@ya.ru

Статья поступила 28 декабря 2015 г.
Исправленный вариант — 28 марта 2016 г.

Литература

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

[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

[3] Ильев В. П., Ильева С. Д., Навроцкая А. А. Приближённые алгоритмы для задач аппроксимации графов // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 1. С. 41–60.

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

[5] Ильев В. П., Навроцкая А. А. Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера // Прикл. дискрет. математика. 2011. № 3. С. 80–84.

[6] Ильев В. П., Навроцкая А. А. Приближённое и точное решение одного варианта задачи кластеризации взаимосвязанных объектов // Тр. XI междунар. Азиатской школы-семинара «Проблемы оптимизации сложных систем» (Чолпон-Ата, 27 июля–7 августа 2015 г.). Новосибирск: Инст. вычисл. математики и мат. геофизики СО РАН, 2015. С. 278–283.

[7] Ляпунов А. А. О строении и эволюции управляющих систем в связи с теорией классификации // Пробл. кибернетики. М.: Наука, 1973. Вып. 27. С. 7–18.

[8] Фридман Г. Ш. Одна задача аппроксимации графов // Управляемые системы. 1971. Вып. 8. С. 73–75.

[9] Фридман Г. Ш. Исследование одной задачи классификации на графах // Методы моделирования и обработка информации. Новосибирск: Наука, 1976. С. 147–177.

[10] Ailon N., Charikar M., Newman A. Aggregating inconsistent information: Ranking and clustering // J. ACM. 2008. Vol. 55, No. 5. P. 1–27.

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

[12] Ben-Dor A., Shamir R., Yakhimi Z. Clustering gene expression patterns // J. Comput. Biol. 1999. Vol. 6, No. 3–4. P. 281–297.

[13] Charikar M., Guruswami V., Wirth A. Clustering with qualitative information // J. Comput. Syst. Sci. 2005. Vol. 71, No. 3. P. 360–383.

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

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

[16] Krivánek M., Morávek J. NP-hard problems in hierarchical-tree clustering // Acta Inf. 1986. Vol. 23. P. 311–323.

[17] Schaeffer S. E. Graph clustering // Comput. Sci. Rev. 2007. Vol. 1, No. 1. P. 27–64.

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

[19] Tomescu I. La reduction minimale d’un graphe à une reunion de cliques // Discrete Math. 1974. Vol. 10, No. 1–2. P. 173–179.

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