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

В 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>. Насколько это больше по сравнению с объективным значением, которое дает релаксация полуопределенного программирования, то есть каков коэффициент аппроксимации?