Минимальная бисекция: различия между версиями

'''Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, <math>\beta</math>-сбалансированном сечении и заранее заданном разбиении с фиксированным r могут быть приближенно решены за полиномиальное время с коэффициентом O(log n).'''

Алгоритмы из вышеприведенных теорем используют (в качестве черного ящика) аппроксимационный алгоритм для задачи под названием «разрез с минимальным частным» или эквивалентной ей задачи нахождения самого разреженного сечения с равномерным спросом (?). Лучшие из известных на данный момент аппроксимационные алгоритмы с коэффициентом <math>O( \sqrt{log \; n})</math> для решения этой задачи для графов общего вида предложили Арора, Рао и Вазирани [2], а алгоритм для графов, не включающих фиксированный минор, с временем выполнения O(1) – Кляйн, Плоткин и Рао. Эти аппроксимационные алгоритмы для вычисления разреза с минимальным частным позволяют получить аппроксимационный алгоритм по двум критериям с полиномиальным временем выполнения (иногда называемый алгоритмом псевдоаппроксимации) для решения задачи о минимальной бисекции. Например, для графов общего вида алгоритм гарантированно вычисляет 2/3-сбалансированный разрез со стоимостью не более <math>O( \sqrt{log \; n}) \cdot b(G)</math>. Отметим, впрочем, что 2/3-сбалансированный разрез не является хорошей аппроксимацией для значения b(G). Например, если граф G состоит из трех непересекающихся клик равного размера, оптимальный 2/3-сбалансированный разрез не содержит ребер, тогда как <math>b(G) = \Omega(n^2) \;</math>. Информацию о других работах в этом направлении, включая аппроксимационные алгоритмы для плотных графов, для ориентированных графов, а также для других задач о разбиении графов см. в главе 1 [6] и по ссылкам, приведенным в этой работе.

*'' [[Самое разреженное сечение]]