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

Последнее ограничение может быть ослаблено так, что каждое <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.

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

Делорм и Поляк [ ] представили верхнюю границу собственного значения для величины максимального разреза, которая является усиленной версией предыдущей границы собственного значения, рассмотренной Мохаром и Поляком [ ]. Вычисление верхней границы Делорма и Поляка эквивалентно решению задачи минимизации собственных значений. Они показали, что их граница вычисляется за полиномиальное время с произвольной точностью. В ряде работ Делорм, Поляк и Рендл показали, что эта верхняя граница ведет себя «иначе», чем верхние границы, основанные на линейном программировании. Например, они изучили классы разреженных случайных графов (такие как G(n,p) с p = 50/n) и показали, что на таких графах их верхняя граница близка к оптимальной [ ]. Поскольку графы такого типа также могут использоваться для демонстрации разрыва целостности, произвольно близкого к 2, для вышеупомянутых релаксаций линейного программирования, их работа подчеркнула разницу в поведении этих двух верхних границ. Последующие вычислительные эксперименты на других классах графов дали больше доказательств того, что эта граница действительно сильнее ранее изученных [27, 29]. Делорм и Поляк предположили, что 5-цикл демонстрирует поведение наихудшего случая для их границы: отношение 32/(25 + 5p5) ^ :88445 между их границей и оптимальным целочисленным решением. Однако они не смогли доказать, что их граница строго меньше удвоенной величины максимального разреза в наихудшем случае.