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

  1. Историческая справка
    1. Ф.Ф., 1955
    2. Edmonds-Karp., 1969 (идея кратчайших путей)
    3. Dinic, 1970 (блокирующий поток на сети кратчайших путей)
    4. Edmonds-Karp, Dinic, 1972 (масштабирование потока)
    5. Malhotra-Kumar-Maheshwari, 1978 (оптимизация Диница до V3) (в нашем курсе этого нет)
    6. Goldberg, Rao, 1998, Лучшее время на текущий момент: E*min(V2/3, E1/2)*log(V2/E) (в нашем курсе этого нет)
    7. Орлин и компания (Рао, Тарьян, Кинг). Поток за O(VE) и ещё более хорошие времена в отдельных случаях [сайт Орлина]
  2. Техника preflow push (Karzanov, 1974)
    1. Определение preflow. Инициализация. Операции push & relabel.
    2. Корректность тривиального алгоритма (в конце мы получим поток, данный поток максимальный).
    3. Алгоритм за O(V3): while (1) for(v) if (ex[v]) { try to push, try to relabel } (если пробегать лишь очередь вершин с избытком, получаем round robin; move-to-front, fifo − излишне усложнённые той же идеи)
  3. Техника preflow push - 2
    1. Queue optimization
    2. Global-Relabeling optimization
    3. Короткий и быстрый алгоритм: while (1) { for(e) try to push ; global relabeling }
    4. High-Level optimization (Cherkassky, 1977, O(n2sqrt(m)))
    5. Ahuja : масштабирование потока + preflow (Ahuja, Orlin, 1986)
  4. Глобальный разрез
    1. Алгоритм Штор-Вагнера за O(V3) (Wagner, Stoer, 1997)
    2. Алгоритм Каргера-Штейна, версия за O(V4)
    3. Алгоритм Каргера-Штейна, версия за O(V2logV) (Karger, Stein, 1993)