ICS 269, Spring 1998: Theory Seminar
22 May 1998:
New Fast Network Flow Algorithms
Yi Cao, ICS, UC
Irvine
Yi described a FOCS '97 paper by Andrew Goldberg and Satish Rao,
"Beyond the Flow Decomposition Barrier". This paper introduces a
new approach to the maximum flow problem based on the blocking flow
method, with arc lengths assigned according to the residual flow
value and residual capacities. Their approach leads to an
O(min(n2/3, m1/2)
m log(n2/m) log U) time
bound for a network with n vertices, m arcs and
integral arc capacities in the range [1,...,U].