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

Работа Гуманса и Уильямсона открыла путь для последующего применения полуопределенного программирования в алгоритмах аппроксимации, в частности, в задачах разбиения графов. Методы, основанные на технике случайных гиперплоскостей, были успешно применены ко многим оптимизационным задачам, которые можно отнести к задачам разбиения. Можно привести такие примеры, как 3-раскраска (3-COLORING) [17], максимальный тройной разрез (MAX-3-CUT) [10, 12, 22], максимальная бисекция (MAX-BISECTION) [15], корреляционная кластеризация (CORRELATION-CLUSTERING) [5, 32] и [[самый неплотный разрез]] (SPARSEST-CUT) [2]. Кроме того, был достигнут определенный прогресс в расширении методов полуопределенного программирования за пределы области разбиения графов на такие задачи, как промежуточность (BETWEENNESS) [6], пропускная способность (BANDWIDTH) [4] и линейные уравнения с модулем p (LINEAR EQUATIONS modp) [1].