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

Эквивалентность этих двух релаксаций обусловлена тем, что матрица Y является положительно полуопределенной тогда и только тогда, когда существует матрица B такая, что BT B = Y. Последняя релаксация может быть решена с произвольной точностью за полиномиальное время с помощью метода эллипсоидов, поскольку имеет полиномиальный по времени оракул разделения [14]. Таким образом, решение первой релаксации можно получить, найдя решение второй релаксации и найдя матрицу B такую, что BTB = Y. Если столбцы B соответствуют векторам fvig, то yij = vi ■ vj, что дает решение первой релаксации.

Гёманс и Уильямсон показали, как округлить релаксацию полуопределенного программирования MAX-CUT с помощью новой техники, которая с тех пор стала называться округлением с помощью случайной гиперплоскости (random-hyperplane rounding) [ ]. Вначале получим решение первой релаксации, которое состоит из набора единичных векторов fvig, по одному вектору для каждой вершины. Затем выберем случайный вектор r 2 Rn, каждая координата r которого выбирается из стандартного нормального распределения. Наконец, положим S = {i\vj-r > 0g и выведем разрез (S; V n S).

Вероятность того, что конкретное ребро (i;j) 2 E пересекает разрез, равна вероятности того, что скалярные произведения vi ■ r и vj ■ r различаются по знаку. Эта вероятность в точности равна Qjjln, где 9jj – угол между векторами vi и vj. Таким образом, ожидаемый вес ребер, пересекающих разрез, равен P(i;j )2E OJJITI. Насколько это больше по сравнению с объективным значением, которое дает релаксация полуопределенного программирования, то есть каков коэффициент аппроксимации?