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

Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) алгоритм аппроксимации для решения задачи о минимальной бисекции в k-однородных гиперграфах [ ]; (2) алгоритм аппроксимации для варианта задачи о минимальном множественном разрезе [ ]; (3) алгоритм эффективного определения невыполнимости случайных булевых формул в 2k-конъюнктивной нормальной форме (2k-SAT) при достаточно большом количестве дизъюнктов [5].

С учетом практического подхода были предложены и изучены многочисленные эвристики (алгоритмы без гарантии для наихудшего случая) для разбиения графов; их комплексный обзор можно найтив [ ]. Одной из самых известных является эвристика локального поиска Лина-Кернигана для минимальной бисекции [11].