Бонусная лекция. Глобальные разрезы (13 марта 2014)

1. Формулировка. Разбить V на S + T: C(S, T) = min
2. Наивный алгоритм: перебрать s, найти minCut(1, s)
3. Алгоритм Штор-Вагнера за O(n*Dijkstra)
1. Найдем какие-то s, t и minCut(s, t), после этого или Answer = minCut(s, t), или s и t можно стянуть в одну вершину
2. A₁ = {1}, A_i+1 = A_i + {a_i = вершина с минимальной суммой пропускных способностей по ребрам из нее в A_i}
3. t = a_n, s = a_n-1. minCut(t, s) : T = {t}, S = V - {t}
4. Вероятностный алгоритм Каргера-Штейнера за O(n²logn) с вероятностью успеха 1/2
1. Все пропускные способности равны 1, но разрешены мультиребра. Если хотим добавить ребро целой пропускной способности k, добавляем k единичных ребер.
2. min deg = k. global min cut ≤ k. |E| ≥ |V|k/2
3. выберем случайное ребро, с вероятностью minCut/E ≤ k/E = 2/|V| оно лежит в мин.разрезе, иначе его концы можно стянть в одну вершину
4. Алгоритм #1: стягиваем, пока не останется 2 вершины, вероятность того, что ни разу не ошиблись = (|V|-2)/|V| * (|V|-3)/(|V|-1) * ... = Θ(|V|^-2)
5. Повторим этот процесс |V|² раз, получим алгоритм за |V|⁴ с вероятностью успеха 1/2
6. Алгоритм #2: делаем первые |V|/2 стягиваний, а затем ветвимся. После |V|/2 стягиваний, мы нигде не ошиблись с вероятностью 1/4. В этот делаем два рекурсивных запуска.
7. Получили p_k = 1/4 * (1 - (1 - p_k-1)²), p_k ≈ 1/k, т.е. вероятность успеха = 1/log|V|
8. T(n) = n² + 2T(n/2), докажем, что T(n) ≤ 2n²
9. Итого алгоритм с временем работы n²logn и вероятностью успеха 1/2