Max flows in O(nm) time, or better
Speaker: James Orlin, MIT, Sloan
Date: Tuesday, October 2 2012
Time: 4:15PM to 5:15PM
Refreshments: 3:45PM
Location: *Note*: 32-141
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: 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.
See other events that are part of Theory Colloquium 2012/2013
See other events happening in October 2012
