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

Определим agw как отношение ожидаемого вклада ребра в разрез к его вкладу в целевую функцию релаксации полуопределенного программирования в наихудшем случае. Иными словами, agw = тт0<д<л -^ 1_^OSQ ■. Можно показать, что agw > 0,87856. Таким образом, ожидаемое значение разреза не меньше agw ■ SDPOPT, что дает коэффициент аппроксимации не менее 0,87856 для задачи MAX-CUT. Аналогичный анализ применим к взвешенным графам с неотрицательными весами ребер.

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