Fall 2012 Seminar Series

DATE: October 2nd
LOCATION: 32-124
TIME: 4:15pm
Reception immediately following

SPEAKER:
James Orlin

TITLE
Max Flows in O(nm) Time, or Better

ABSTRACT
In this paper, we present improved polynomial time algorithms for the max flow problem defined on a network with n nodes and m arcs. We show how to solve the max flow problem in O(nm) time, improving upon the best previous algorithm due to King, Rao, and Tarjan, who solved the max flow problem in O(nm log_{m/(n log n)}n) time. In the case that m = O(n), we improve the running time to O(n^2/log n). We further improve the running time in the case that U^* = U_{max}/U_{min} is not too large, where U_{max} denotes the largest finite capacity and U_{min} denotes the smallest non-zero capacity. If log(U^*) = O(n^{1/3} \log^{-3} n), we show how to solve the max flow problem in O(nm / log n) steps. In the case that log(U^*) = O(\log^k n) for some fixed positive integer k, we show how to solve the max flow problem in O(n^{8/3}) time up to poly-logarithmic factors. This latter algorithm relies on a subroutine for fast matrix multiplication.

 

Joint seminar with CSAIL Theory of Computation (TOC) group