4551
правка
Минимальная бисекция: различия между версиями
Материал из WEGA
→Родственные работы
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 80: | Строка 80: | ||
== Родственные работы == | == Родственные работы == | ||
Алгоритм аппроксимации по двум критериям для нахождения f$-сбалансированного разреза возвращает разрез, являющийся /^'-сбалансированным для заранее определенного значения /}' > p. Например, для бисекции, P = 1/2; обычно P' = 2/3. | |||
Алгоритмы из вышеприведенных теорем используют (в качестве черного ящика) алгоритм аппроксимации для задачи под названием «разрез с минимальным частным» или эквивалентной ей задачи нахождения самого неплотного сечения с равномерным спросом (?). Лучших из известных на данный момент алгоритмов аппроксимации с коэффициентом O(log n) для решения этой задачи для графов общего вида предложили Арора, Рао и Вазирани [2], а алгоритм для графов, не включающих фиксированный минор, с временем выполнения O(1) – Кляйн, Плоткин и Рао. Эти алгоритмы аппроксимации для вычисления разреза с минимальным частным позволяют получить алгоритм аппроксимации по двум критериям с полиномиальным временем выполнения (иногда называемый алгоритмом псевдоаппроксимации) для решения задачи о минимальной бисекции. Например, для графов общего вида алгоритм гарантированно вычисляет 2/3-сбалансированный разрез со стоимостью не более O(logn) • b(G). Отметим, впрочем, что 2/3-сбалансированный разрез не является хорошей аппроксимацией для значения b(G). Например, если граф G состоит из трех непересекающихся клик равного размера, оптимальный 2/3-сбалансированный разрез не содержит ребер, тогда как b(G) = Q(n2). Информацию о других работах в этом направлении, включая алгоритмы аппроксимации для плотных графов, для ориентированных графов, а также для других задач о разбиении графов см. в главе 1 [ ] и по ссылкам, приведенным в этой работе. | |||
