Что: | Лекция |
Когда: | Вторник, 03 июня 2008, 13:00–15:00 |
Где: | ПОМИ РАН |
Слайды: | graphalgorithms_lecture_030608.pdf |
The maximum flow problem is a classical combinatorial optimization problem with numerous applications. Efficient algorithms for this problem have been studied for over half a century. For a long time, the $ O(nm) $ has been the goal of the algorithm designers, where $ n $ and $ m $ are the number of input vertices and arcs, respectively. This is a natural target as the maximum flow decomposition can have $ \Omega(nm) $ arcs. Algorithms achieving the bound for most graph densities, and coming within a factor of $ \log n $ or less for the remaining ones, have been developed. However, for the unit capacity case, the problem can be solved in $ O(\min(n^{2/3}, m^{1/2})\cdot m) $ time. The binary blocking flow algorithm extends this result to the case of integral capacities in the range $ [1\dots U] $ and achieves the bound of $ O(\min(n^{2/3}, m^{1/2})\cdot m\cdot\log(n^2/m)\cdot\log U) $. This bound is better that $ O(nm) $ unless $ U $ is huge. Whereas the previous algorithms treated all residual arcs equally, assigning them length one, our algorithm distinguishes between small and large arcs, assigning length one to the former and length zero to the latter. In this talk we describe the binary blocking flow algorithm and its analysis. We also discuss related open problems: extending the result to minimum-cost flows and obtaining practical improvements based on the ideas of the algorithm.