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

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