Максимальный разрез (Max-Cut) и полуопределенное программирование
Мы уже обсуждали задачу о минимальном разрезе (Min-Cut), которая изящно решается через алгоритмы максимального потока (или рандомизированный алгоритм Каргера). Кажется логичным, что если изменить слово "минимальный" на "максимальный", задача останется такой же легкой. Но в дискретной математике интуиция часто обманчива. Задача о Максимальном разрезе (Max-Cut) является одной из самых сложных NP-полных проблем, лежащей в основе статистической физики (модели спиновых стекол) и проектирования VLSI-чипов.
Суть задачи Max-Cut: нужно разделить все вершины графа на две непересекающиеся группы так, чтобы максимизировать количество ребер, которые проходят между этими двумя группами. Если мы просто раскидаем вершины по двум группам абсолютно случайным образом, бросая монетку, каждое ребро окажется "разрезанным" с вероятностью 50%. Это дает нам тривиальный приближенный алгоритм с коэффициентом 0.5 (мы найдем разрез, который как минимум в два раза хуже абсолютного математического максимума).
Десятилетиями никто не мог улучшить эту оценку 0.5. Настоящий прорыв произошел в 1995 году, когда Мишель Гоеманс и Дэвид Уильямсон применили к графам мощнейший аппарат из непрерывной математики — Полуопределенное программирование (Semidefinite Programming, SDP).
Алгоритм Гоеманса-Уильямсона использует гениальную векторную релаксацию:
- Вместо того чтобы присваивать вершине графа строгое скалярное значение +1 (левая группа) или -1 (правая группа), алгоритм превращает каждую вершину в n-мерный вектор единичной длины на многомерной сфере.
- Задача максимизации разреза переформулируется на языке векторной алгебры: нужно раздвинуть векторы смежных вершин так, чтобы угол между ними был максимально близок к 180 градусам (чтобы они "смотрели" в разные стороны). Эта задача является выпуклой и легко решается матричными солверами за полиномиальное время.
- Случайное округление: когда оптимальные векторы на многомерной сфере найдены, алгоритм проводит через центр сферы абсолютно случайную гиперплоскость, которая разрезает сферу пополам. Векторы, оказавшиеся по одну сторону гиперплоскости, назначаются в группу +1, по другую — в группу -1.
Математический анализ с использованием тригонометрических тождеств доказал, что этот метод гарантированно находит разрез, который составляет не менее 0.87856... от идеального максимума. Позднее, в рамках Гипотезы уникальных игр (Unique Games Conjecture), Субхаш Хот предположил, что улучшить коэффициент 0.878 алгоритмически вообще невозможно, если только P не равно NP. Алгоритм Гоеманса-Уильямсона стал эталоном того, как абстрактная многомерная геометрия помогает взламывать дискретные NP-задачи.
