ICS Theory Group

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/3m1/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].