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

Пусть имеется неориентированный граф G = (V, E). Задача о максимальном разрезе (MAX-CUT) заключается в нахождении такого биразбиения вершин, при котором суммарный вес ребер, пересекающих это разбиение, оказывается максимальным. Если веса ребер неотрицательны, то эта задача эквивалентна нахождению подмножества ребер с максимальным весом, которое образует двудольный подграф, то есть задаче о максимальном двудольном подграфе. Все результаты, обсуждаемые далее в статье, предполагают неотрицательные веса ребер. MAX-CUT входит в число изначальных NP-полных задач Карпа [19] [https://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%9A%D0%B0%D1%80%D0%BF%D0%B0]. На самом деле она является NP-трудной для аппроксимации с точностью до коэффициента, лучшего, чем 16/17 [16, 33].

Делорм и Поляк [7] представили верхнюю границу собственного значения для величины максимального разреза, которая является усиленной версией предыдущей границы собственного значения, рассмотренной Мохаром и Поляком [24]. Вычисление верхней границы Делорма и Поляка эквивалентно решению задачи минимизации собственных значений. Они показали, что их граница вычисляется за полиномиальное время с произвольной точностью. В ряде работ Делорм, Поляк и Рендл показали, что эта верхняя граница ведет себя «иначе», чем верхние границы, основанные на линейном программировании. Например, они изучили классы разреженных случайных графов (такие как G(n,p) с p = 50/n) и показали, что на таких графах их верхняя граница близка к оптимальной [8]. Поскольку графы такого типа также могут использоваться для демонстрации разрыва целостности, произвольно близкого к 2, для вышеупомянутых релаксаций линейного программирования, их работа подчеркнула разницу в поведении этих двух верхних границ. Последующие вычислительные эксперименты на других классах графов дали больше доказательств того, что эта граница действительно сильнее ранее изученных [27, 29]. Делорм и Поляк предположили, что 5-цикл демонстрирует поведение наихудшего случая для их границы: отношение <math>32/(25 + 5 \sqrt{5}) \approx 0,88445</math> между их границей и оптимальным целочисленным решением. Однако они не смогли доказать, что их граница строго меньше удвоенной величины максимального разреза в наихудшем случае.

В 1994 году Гуманс и Уильямсон представили рандомизированный алгоритм решения задачи MAX-CUT с коэффициентом аппроксимации 0,87856 [11]. Их прорывная работа была основана на округлении релаксации полуопределенного программирования [https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D1%83%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D1%91%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5] и стала первым случаем применения этого метода в алгоритмах аппроксимации. Поляк и Рендл показали, что верхняя граница, достигаемая этой полуопределенной релаксацией, эквивалентна границе собственных значений Делорма и Поляка [28]. Таким образом, Гёеманс и Уильямсон доказали, что собственное значение Делорма и Поляка не более чем в 1,138 раза превышает величину максимального разреза.

Они показали, что данная релаксация эквивалентна полуопределенной программе. Рассмотрим следующую полуопределенную релаксацию:

Гуманс и Уильямсон показали, как округлить релаксацию полуопределенного программирования MAX-CUT с помощью новой техники, которая с тех пор стала называться округлением с помощью случайной гиперплоскости (random-hyperplane rounding) [11]. Вначале получим решение первой релаксации, которое состоит из набора единичных векторов <math>\{ v_i \}</math>, по одному вектору для каждой вершины. Затем выберем случайный вектор <math>r \in \mathcal{R}^n</math>, каждая координата <math>r</math> которого выбирается из стандартного нормального распределения. Наконец, положим <math>S = \{ i | vi \cdot r \ge 0 \}</math> и выведем разрез (S, V \ S).

Вероятность того, что конкретное ребро <math>(i, j) \in E</math> пересекает разрез, равна вероятности того, что скалярные произведения <math>v_i \cdot r</math> и <math>vj \cdot r</math> различаются по знаку. Эта вероятность в точности равна <math>\theta_{ij} / \pi</math>, где <math>\theta_{ij}</math> – угол между векторами <math>v_i</math> и <math>v_j</math>. Таким образом, ожидаемый вес ребер, пересекающих разрез, равен <math>\sum_{(i, j) \in E} \theta_{ij} / \pi</math>. Насколько это больше по сравнению с объективным значением, которое дает релаксация полуопределенного программирования, то есть каков коэффициент аппроксимации?

Карлофф показал, что существуют графы, для которых наилучшая гиперплоскость лишь на коэффициент <math>\alpha_{gw}</math> отличается от максимального разреза [18], продемонстрировав , что существуют графы, для которых анализ в работе [11] является строгим. Поскольку оптимальное значение разрыва целостности в задаче полуопределенного программирования (SDP) для таких графов равно оптимальной величине максимального разреза, эти графы не могут быть использованы для демонстрации разрыва целостности. Однако Фейге и Шехтман показали, что существуют графы, для которых максимальный разрез составляет <math>\alpha_{gw}</math>-долю от границы SDP [9], тем самым установив, что гарантия аппроксимации алгоритма Гуманса и Уильямсона соответствует разрыву целостности в их релаксации полуопределенного программирования. Недавно Хот, Киндлер, Моссел и О'Доннел [21] показали, что если предположить, что гипотеза об уникальной игре Хота [20] верна, то аппроксимация MAX-CUT с точностью до любого коэффициента, большего <math>\alpha_{gw}</math>, является NP-трудной задачей.

Работа Гуманса и Уильямсона открыла путь для последующего применения полуопределенного программирования в алгоритмах аппроксимации, в частности, в задачах разбиения графов. Методы, основанные на технике случайных гиперплоскостей, были успешно применены ко многим оптимизационным задачам, которые можно отнести к задачам разбиения. Можно привести такие примеры, как 3-раскраска (3-COLORING) [17], максимальный тройной разрез (MAX-3-CUT) [10, 12, 22], максимальная бисекция (MAX-BISECTION) [15], корреляционная кластеризация (CORRELATION-CLUSTERING) [5, 32] и [[самый неплотный разрез]] (SPARSEST-CUT) [2]. Кроме того, был достигнут определенный прогресс в расширении методов полуопределенного программирования за пределы области разбиения графов на такие задачи, как промежуточность (BETWEENNESS) [6], пропускная способность (BANDWIDTH) [4] и линейные уравнения с модулем p (LINEAR EQUATIONS modp) [1].

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