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

В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали алгоритм аппроксимации по двум критериям для решения задачи о минимальной бисекции с логарифмическим коэффициентом. Этот алгоритм нашел множество приложений, однако вопрос поиска настоящего алгоритма аппроксимации со схожим коэффициентом оставался открытым еще десять лет. В 1999 году Файге и Краутгамер [6] предложили первый алгоритм аппроксимации солиномиальным временем выполнения, который аппроксимирует задачу с полилогарифмическим относительно размера графа коэффициентом.

(Алгоритм аппроксимации по двум критериям разбивает вершины на два множество, каждое из которых содержит не более 2/3 вершин, и его значение (т.е. количество ребер, соединяющих множества) сравнивается со значением наилучшего разбиения на множества равного размера).

Фейге и Краутхамер [6] предложили алгоритм аппроксимации для задачи о минимальной бисекции. Изначально они получили коэффициент апрроксимации <math>O(log^2 \; n)</math>, поскольку в их подходе использовался алгоритм Лейтона и Рао [14]; однако, применив вместо него алгоритм из [2], авторы улучшили коэффициент до <math>O(log^{1,5} \; n)</math>.

Алгоритм аппроксимации по двум критериям для нахождения <math>\beta</math>-сбалансированного разреза возвращает разрез, являющийся <math>\beta'</math>-сбалансированным для заранее определенного значения <math>\beta' > \beta \;</math>. Например, для бисекции <math>\beta = 1/2 \;</math> и чаще всего <math>\beta' = 2/3 \;</math>.

Алгоритмы из вышеприведенных теорем используют (в качестве черного ящика) алгоритм аппроксимации для задачи под названием «разрез с минимальным частным» или эквивалентной ей задачи нахождения самого неплотного сечения с равномерным спросом (?). Лучших из известных на данный момент алгоритмов аппроксимации с коэффициентом <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] и по ссылкам, приведенным в этой работе.

Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) алгоритм аппроксимации для решения задачи о минимальной бисекции в k-однородных гиперграфах [3]; (2) алгоритм аппроксимации для варианта задачи о минимальном множественном разрезе [17]; (3) алгоритм эффективного определения невыполнимости случайных булевых формул в 2k-конъюнктивной нормальной форме (2k-SAT) при достаточно большом количестве дизъюнктов [5].

В настоящее время существует большой разрыв между коэффициентом аппроксимации O(log n) для задачи о минимальной бисекции, полученным в результате применения теоремы 1, и сложностью известных для него результатов аппроксимации. Как упоминалось выше, задача о минимальной бисекции является NP-полной [9].

Неизвестно, является ли эта задача APX-полной, однако некоторые результаты позволяют предположить такую возможность. Буй и Джонс [4] показали, что для любого фиксированного значения e > 0 задача аппроксимации минимальной бисекции с дополнительным членом и2~е будет NP-полной. Фейге [ ] показал, что если опровержение для задачи выполнимости булевых формул в k-конъюнктивной нормальной форме в случае k=3 является сложным в среднем на реальном распределении входных данных, то для любого фиксированного значения " > 0 не существует алгоритма 4/3-аппроксимации задачи о минимальной бисекции. Хот [ ] доказал, что для нахождения минимальной бисекции неприменима схема аппроксимации с полиномиальным временем выполнения (PTAS), за исключением случая, если класс NP включает рандомизированные алгоритмы с субэкспоненциальным временем выполнения.

Версия с вершинным разрезом задачи о минимальном разрезе определяется следующим образом. Цель состоит в разбиении вершин входного графа на множества V = A [ B [ S, где |S| насколько возможно мало, при соблюдении следующего ограничения: max fjAj; jBjg < n/2 и ни одно ребро не связывает множества A и B. Неизвестно, можно ли получить алгоритм аппроксимации с полилогарифмическим коэффициентом для решения этой задачи. Стоит отметить, что на тот же вопрос, касающийся версии задачи о минимальной бисекции для ориентированных графов, Фейгеи Яхалом дали отрицательный ответ [8].

 

*'' [[Самое неплотное сечение]]