Генерический подход к алгоритмическим проблемам предложен Мясниковым, Каповичем, Шуппом и Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность проблемы кластеризации графов. В этой задаче структура взаимосвязей объектов задаётся с помощью графа, вершины которого соответствуют объектам, а рёбра соединяют похожие объекты. Требуется разбить множество объектов на попарно непересекающиеся группы (кластеры) так, чтобы минимизировать число связей между кластерами и число недостающих связей внутри кластеров. Доказывается, что при условии P = NP и P = BPP для проблемы кластеризации графов не существует полиномиального сильно генерического алгоритма. Сильно генерический алгоритм решает проблему не на всём множестве входов, а на подмножестве, последовательность частот которого при увеличении размера экспоненциально быстро сходится к 1.
Скачать электронную версию публикации
Загружен, раз: 100
- Title О генерической сложности проблемы кластеризации графов
- Headline О генерической сложности проблемы кластеризации графов
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 46
- Date:
- DOI 10.17223/20710410/46/6
Ключевые слова
генерическая сложность, кластеризация графа, generic complexity, graph clusteringАвторы
Ссылки
Kapovich I., Miasnikov A., Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. V. 264. No. 2. P. 665-694
Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. 1975. Т. 31. С. 35-42
Krivanek, M., and Moravek, J. NP-hard problems in hierarchical-tree clustering // Acta Informatica. 1986. V. 23. P. 311-323
Bansal N., Blum A., and Chawla S. Correlation clustering // Machine Learning. 2004. V. 56. P. 89-113
Shamir R., Sharan R., and Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. V. 144. No. 1-2. P. 173-182
Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С. Вычислительная сложность задачи аппроксимации графов // Дискретный анализ и исследование операций. Сер. 1. 2006. Т. 13. № 1. С. 3-11
Ильев В. П., Ильева С. Д. О задачах кластеризации графов // Вестник Омского университета. 2016. № 2. C. 16-18
Ильев А. В., Ильев В. П. Об одной задаче кластеризации графа с частичным обучением // Прикладная дискретная математика. 2018. № 42. С. 66-75
Талевнин А. С. О сложности задачи аппроксимации графов // Вестник Омского университета. 2004. № 4. C. 22-24
Impagliazzo R. and Wigderson A. P = BPP unless E has subexponential circuits: Derandomizing the XOR Lemma // Proc. 29th STOC. El Paso: ACM, 1997. P. 220-229
Рыбалов А. Н. О генерической сложности проблемы общезначимости булевых формул // Прикладная дискретная математика. 2016. № 2(32). С. 119-126
О генерической сложности проблемы кластеризации графов | Прикладная дискретная математика. 2019. № 46. DOI: 10.17223/20710410/46/6
Скачать полнотекстовую версию
Загружен, раз: 432