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

На протяжении почти двадцати лет лучшим известным коэффициентом аппроксимации для MAX-CUT был 1/2, который можно получить с помощью очень простого алгоритма. Сформируем множество S, помещая каждую вершину в S с вероятностью 1/2. Поскольку каждое ребро пересекает разрез (S, V \ S) с вероятностью 1/2, ожидаемая [[Величина разреза|величина]] этого разреза равно половине суммарного веса ребер. Отсюда следует, что для любого графа существует разрез с величиной не менее половины суммарного веса ребер. В 1976 году Сахни и Гонсалес представили детерминированный полуаппроксимационный алгоритм для задачи MAX-CUT, который, по сути, представляет собой дерандомизацию вышеупомянутого рандомизированного алгоритма [31]. Выполним итеративный обход вершин и сформируем множества <math>S</math> и <math>\bar{S}</math>, помещая каждую вершину в то из них, которое максимизирует вес разреза <math>(S, \bar{S})</math> на текущий момент. После каждой итерации этого процесса вес этого разреза составит не менее половины суммарного веса ребер, конечные точки которых находятся в <math>S \cup \bar{S}</math>.

Было показано, что для многих задач оптимизации (максимизации) линейное программирование [https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%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] дает лучшие верхние границы на величину оптимального решения, чем те, которые можно получить с помощью комбинаторных методов. Существует несколько хорошо изученных релаксаций линейного программирования для задачи MAX-CUT. Например, в классической целочисленной программе имеются переменная <math>x_e</math> для каждого ребра и ограничение для каждого нечетного цикла, требующее, чтобы нечетный цикл C вносил не более |C|-1 ребер в оптимальное решение.

<math>\sum_{e \in E} w_e x_e</math>

Последнее ограничение может быть ослаблено так, что каждое <math>x_e</math> должно лежать между 0 и 1, но не обязательно должно быть целым, то есть <math>0 \le x_e \le 1</math>. Хотя у этой релаксации может быть экспоненциальное число ограничений, существует оракул разделения с полиномиальным временем работы (эквивалентный нахождению нечетного цикла минимального веса) и, таким образом, эта релаксация может быть решена за полиномиальное время [13]. Другая классическая целочисленная программа содержит переменную <math>x_{ij}</math> для каждой пары вершин. При любом разбиении вершин разрез пересекают либо ноль, либо два ребра из 3-цикла. Это требование выполняется в следующей целочисленной программе. Если ребро <math>(i, j) \ne E</math>, то <math>w_{ij}</math> присваивается значение 0.

Опять же, последнее ограничение может быть ослаблено таким образом, что каждый xij должен лежать между 0 и 1. В отличие от вышеупомянутой линейной программы, основанной на ограничениях цикла, данная релаксация ЛП имеет полиномиальное число ограничений.

Обе эти релаксации фактически имеют одно и то же оптимальное значение для любого графа с неотрицательными весами ребер [3, 26, 30]. Упрощенное доказательство этого можно найти в работе [25]. Поляк показал, что разрыв целостности для каждой из этих релаксаций произвольно близок к 2 [26]. Иными словами, существуют классы графов, у которых максимальный разрез содержит около половины ребер, но для которых каждая из приведенных выше релаксаций дает верхнюю границу, близкую ко всем ребрам, то есть не лучше, чем тривиальная «всереберная» граница. В частности, для демонстрации этого разрыва можно использовать графы с максимальным разрезом, близким к половине ребер, и с высоким обхватом. Полный обзор этих релаксаций линейного программирования содержится в обзоре Поляка и Тузы [30].