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

В 1994 году Гуманс и Уильямсон представили рандомизированный алгоритм решения задачи MAX-CUT с коэффициентом аппроксимации 0,87856 [11]. Их прорывная работа была основана на округлении релаксации полуопределенного программирования [https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D1%83%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D1%91%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5] и стала первым случаем применения этого метода в алгоритмах аппроксимации. Поляк и Рендл показали, что верхняя граница, достигаемая этой полуопределенной релаксацией, эквивалентна границе собственных значений Делорма и Поляка [28]. Таким образом, Гёеманс и Уильямсон доказали, что собственное значение Делорма и Поляка не более чем в 1,138 раза превышает значение максимального разреза.

Определим <math>\alpha_{gw}</math> как отношение ожидаемого вклада ребра в разрез к его вкладу в целевую функцию релаксации полуопределенного программирования в наихудшем случае. Иными словами, <math>\alpha_{gw} = min_{0 \le \theta \le \pi} \frac{2}{\pi} \frac{\theta}{1 - cos \theta}</math>. Можно показать, что <math>\alpha_{gw} > 0,87856</math>. Таким образом, ожидаемое значение разреза не меньше <math>\alpha_{gw} \cdot SDP_{OPT}</math>, что дает коэффициент аппроксимации не менее 0,87856 для задачи MAX-CUT. Аналогичный анализ применим к взвешенным графам с неотрицательными весами ребер.

Карлофф показал, что существуют графы, для которых наилучшая гиперплоскость лишь на коэффициент <math>\alpha_{gw}</math> отличается от максимального разреза [18], продемонстрировав , что существуют графы, для которых анализ в работе [11] является строгим. Поскольку оптимальное значение разрыва целостности в задаче полуопределенного программирования (SDP) для таких графов равно оптимальному значению максимального разреза, эти графы не могут быть использованы для демонстрации разрыва целостности. Однако Фейге и Шехтман показали, что существуют графы, для которых максимальный разрез составляет <math>\alpha_{gw}</math>-долю от границы SDP [9], тем самым установив, что гарантия аппроксимации алгоритма Гуманса и Уильямсона соответствует разрыву целостности в их релаксации полуопределенного программирования. Недавно Хот, Киндлер, Моссел и О'Доннел [21] показали, что если предположить, что гипотеза об уникальной игре Хота [20] верна, то аппроксимация MAX-CUT с точностью до любого коэффициента, большего <math>\alpha_{gw}</math>, является NP-трудной задачей.