Потоки-2 (8 апреля 2016)

1. Остаточные сети и теоремы Каразанова
1. Более сильное утверждение − Теорема Карзанова: число итераций алгоритма Диница не более корня из (P = ∑ min(c_in, c_out)). E^3/2 на единичных сетях.
2. Лемма: |f^* - f_k| ≤ U(|V|/L)². Где U − максимальная пропускная способность, L − максимальная длина кратчайшего пути.
3. Вторая Теорема Каразанова. Число итераций алгоритма Диница в графе с целочисленными пропускными способностями не более 2U^1/3|V|^2/3.
2. [L,R]
1. Несколько истоков и стоков.
2. Интересный факт (напоминание): задача про 2 пути NP-трудна
3. Потоки с избытками и недостатками в вершинах.
4. Поиск [L,R] циркуляции
5. Поиск [L,R] потока: решение через Flow
6. Поиск [L,R] потока: решение через MinCostFlow
7. Поиск [L,R] максимального потока: дополнение до максимального

1. Модификая Диница с LinkCut-Tree за O(VElogV).
1. Нарисуем дерево кратчайших путей с корнем в стоке.
2. Возьмём путь от истока до стока. Как за O(logn) учесть этот путь?
2. Глобальный разрез
1. Алгоритм Штор-Вагнера за O(V³) и O(VE + V²logV) (Wagner, Stoer, 1997) (без доказательства)
2. Алгоритм Каргера-Штейна, версия за O(V⁴)
3. Алгоритм Каргера-Штейна, версия за O(V²log²V) (Karger, Stein, 1993) (без доказательства)
3. Историческая справка
1. 1955. Ф.Ф.
2. 1969. Edmonds-Karp. (идея кратчайших путей)
3. 1970. Dinic, (блокирующий поток на сети кратчайших путей)
4. 1972. Edmonds-Karp, Dinic (масштабирование потока)
5. 1978. Malhotra-Kumar-Maheshwari (оптимизация Диница до n³) (в нашем курсе этого нет)
6. 1974. Техника preflow push, Karzanov (первые идеи за n³)
7. 1977. High-Level optimization (Cherkassky, O(n²m^1/2))
8. 1986. Ahuja : масштабирование потока + preflow: O(nm + n²logU) (Ahuja, Orlin)
9. 1998. Goldberg, Rao, Лучшее время на текущий момент: E*min(V^2/3, E^1/2)*log(V²/E) (в нашем курсе этого нет)
10. 2013. Орлин и компания (Рао, Тарьян, Кинг). Поток за O(VE) и ещё более хорошие времена в отдельных случаях [сайт Орлина]