Изучается генерическая сложность проблемы кластеризации графов с ограничением p на размеры кластеров при p ≥ 3. В этой задаче структура взаимосвязей объектов задаётся с помощью графа, вершины которого соответствуют объектам, а рёбра соединяют похожие объекты. Требуется разбить множество объектов на попарно непересекающиеся группы (кластеры) ограниченного числом p размера так, чтобы минимизировать число связей между кластерами и число недостающих связей внутри кластеров. Доказывается, что при условии P ≠ NP и P = BPP для этой проблемы не существует полиномиального сильно генерического алгоритма. Сильно генерический алгоритм решает проблему не на всём множестве входов, а на подмножестве, последовательность частот которого при увеличении размера экспоненциально быстро сходится к 1.
Скачать электронную версию публикации
Загружен, раз: 1
- Title О генерической сложности проблемы кластеризации графов с ограничениями на размер кластеров
- Headline О генерической сложности проблемы кластеризации графов с ограничениями на размер кластеров
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 60
- Date:
- DOI 10.17223/20710410/60/10
Ключевые слова
генерическая сложность, кластеризация графаАвторы
Ссылки
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.
Ильев В. П., Навроцкая А. А. Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера // Прикладная дискретная математика. 2011. №3(13). С. 80-84.
Рыбалов А. Н. О генерической сложности проблемы кластеризации графов // Прикладная дискретная математика. 2019. №46. С. 72-77.
Рыбалов А. Н. О генерической сложности ограниченной проблемы кластеризации графов // Прикладная дискретная математика. 2022. № 57. С. 91-97.
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.
Гимади Э. X., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. 1975. Т. 31. С. 35-42.
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.
Вялый М., Китаев А., Шень А. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо, 1999. 192 с.
О генерической сложности проблемы кластеризации графов с ограничениями на размер кластеров | Прикладная дискретная математика. 2023. № 60. DOI: 10.17223/20710410/60/10
Скачать полнотекстовую версию
Загружен, раз: 122