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

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

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

Было показано, что для многих задач оптимизации (максимизации) линейное программирование дает лучшие верхние границы на значение оптимального решения, чем те, которые можно получить с помощью комбинаторных методов. Существует несколько хорошо изученных релаксаций линейного программирования для задачи MAX-CUT. Например, в классической целочисленной программе имеются переменная xe для каждого ребра и ограничение для каждого нечетного цикла, требующее, чтобы нечетный цикл C вносил не более j C | - 1 ребер в оптимальное решение.