4511
правок
Минимальная бисекция: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 84: | Строка 84: | ||
Алгоритмы из вышеприведенных теорем используют (в качестве черного ящика) алгоритм аппроксимации для задачи под названием «разрез с минимальным частным» или эквивалентной ей задачи нахождения самого неплотного сечения с равномерным спросом (?). Лучших из известных на данный момент алгоритмов аппроксимации с коэффициентом O(log n) для решения этой задачи для графов общего вида предложили Арора, Рао и Вазирани [2], а алгоритм для графов, не включающих фиксированный минор, с временем выполнения O(1) – Кляйн, Плоткин и Рао. Эти алгоритмы аппроксимации для вычисления разреза с минимальным частным позволяют получить алгоритм аппроксимации по двум критериям с полиномиальным временем выполнения (иногда называемый алгоритмом псевдоаппроксимации) для решения задачи о минимальной бисекции. Например, для графов общего вида алгоритм гарантированно вычисляет 2/3-сбалансированный разрез со стоимостью не более O(logn) • b(G). Отметим, впрочем, что 2/3-сбалансированный разрез не является хорошей аппроксимацией для значения b(G). Например, если граф G состоит из трех непересекающихся клик равного размера, оптимальный 2/3-сбалансированный разрез не содержит ребер, тогда как b(G) = Q(n2). Информацию о других работах в этом направлении, включая алгоритмы аппроксимации для плотных графов, для ориентированных графов, а также для других задач о разбиении графов см. в главе 1 [ ] и по ссылкам, приведенным в этой работе. | Алгоритмы из вышеприведенных теорем используют (в качестве черного ящика) алгоритм аппроксимации для задачи под названием «разрез с минимальным частным» или эквивалентной ей задачи нахождения самого неплотного сечения с равномерным спросом (?). Лучших из известных на данный момент алгоритмов аппроксимации с коэффициентом O(log n) для решения этой задачи для графов общего вида предложили Арора, Рао и Вазирани [2], а алгоритм для графов, не включающих фиксированный минор, с временем выполнения O(1) – Кляйн, Плоткин и Рао. Эти алгоритмы аппроксимации для вычисления разреза с минимальным частным позволяют получить алгоритм аппроксимации по двум критериям с полиномиальным временем выполнения (иногда называемый алгоритмом псевдоаппроксимации) для решения задачи о минимальной бисекции. Например, для графов общего вида алгоритм гарантированно вычисляет 2/3-сбалансированный разрез со стоимостью не более O(logn) • b(G). Отметим, впрочем, что 2/3-сбалансированный разрез не является хорошей аппроксимацией для значения b(G). Например, если граф G состоит из трех непересекающихся клик равного размера, оптимальный 2/3-сбалансированный разрез не содержит ребер, тогда как b(G) = Q(n2). Информацию о других работах в этом направлении, включая алгоритмы аппроксимации для плотных графов, для ориентированных графов, а также для других задач о разбиении графов см. в главе 1 [ ] и по ссылкам, приведенным в этой работе. | ||
== Применение == | |||
Важной областью применения для задачи о минимальной бисекции и других задач о разбиении графов является подход «разделяй и властвуй» к решению множества задач оптимизации, особенно на графах – см., например, [15, 16]. Эти задачи естественным образом возникают в разнообразных практических ситуациях – таких как проектирование СБИС и обработка изображений – а также в других сферах, например, в качестве задач кластеризации. | |||
Кроме того, алгоритм минимальной бисекции находит широкое применение в задачах задачах и распределении – в форме, общей для параллельных систем и научных вычислений: необходимо назначать компьютерам задания максимально сбалансированным образом, стараяь присвоить как можно больше определенных фрагментов задания одному компьютеру. Например, рассмотрим ситуацию с назначением n заданий двум компьютерам, для которой известен объем коммуникаций между каждыми двумя заданиями, а цель заключается в обеспечении обоим компьютерам равной нагрузки (количества заданий) и сведения к минимуу количества коммуникаций между компьютерами. Очевидно, что эту задачу можно сформулировать как задачу о минимальной бисекции в подходящим образом сформированном графе. | |||
Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) алгоритм аппроксимации для решения задачи о минимальной бисекции в k-однородных гиперграфах [ ]; (2) алгоритм аппроксимации для варианта задачи о минимальном множественном разрезе [ ]; (3) алгоритм эффективного определения невыполнимости случайных булевых формул в 2k-конъюнктивной нормальной форме (2k-SAT) при достаточно большом количестве дизъюнктов [5]. | |||
С учетом практического подхода были предложены и изучены многочисленные эвристики (алгоритмы без гарантии для наихудшего случая) для разбиения графов; их комплексный обзор можно найтив [ ]. Одной из самых известных является эвристика локального поиска Лина-Кернигана для минимальной бисекции [11]. | |||
== Открытые вопросы == | |||