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

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