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

Этот простой полуаппроксимационный алгоритм использует тот факт, что для любого графа с неотрицательными весами ребер суммарный вес его ребер является верхней границей величины его максимального разреза. Существуют классы графов, для которых максимальный разрез произвольно близок к половине суммарного веса ребер, то есть графы, для которых эта «тривиальная» верхняя граница может быть близка к удвоенному истинному значению оптимального решения. Примером такого класса графов являются полные графы с n вершинами – <math>K_n</math>. Чтобы получить коэффициент аппроксимации лучше 1/2, необходимо уметь вычислять верхнюю границу значения максимального разреза, которая была бы лучше, то есть меньше, тривиальной верхной границы для таких классов графов.

В 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).

Этот алгоритм был дерандомизирован Махаджаном и Харихараном в [23]. Гёманс и Уильямсон также применили свои методы округления с помощью случайной гиперплоскости, чтобы получить улучшенные гарантии аппроксимации для других задач, таких как MAX-DICUT и MAX-2SAT.

Карлофф показал, что существуют графы, для которых наилучшая гиперплоскость лишь на коэффициент <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) [ ]. Кроме того, был достигнут определенный прогресс в расширении методов полуопределенного программирования за пределы области разбиения графов на такие задачи, как промежуточность (BETWEENNESS) [ ], пропускная способность (BANDWIDTH) [ ] и линейные уравнения с модулем p (LINEAR EQUATIONS modp) [1].