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

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

Последнее ограничение может быть ослаблено так, что каждое xe должно лежать между 0 и 1, но не должно быть целым, то есть 0 < xe < 1. Хотя у этой релаксации может быть экспоненциальное число ограничений, существует оракул разделения с полиномиальным временем работы (эквивалентный нахождению нечетного цикла минимального веса) и, таким образом, эта релаксация может быть решена за полиномиальное время [13]. Другая классическая целочисленная программа содержит переменную xij для каждой пары вершин. При любом разбиении вершин разрез пересекают либо ноль, либо два ребра из 3-цикла. Это требование выполняется в следующей целочисленной программе. Если ребро (i; j) ^ E, то wij присваивается значение 0.