ACO/CS Theory Seminar - Solving maximum flows in O(nm) time, and less

Other Talks
Wednesday, May 23, 2012 - 1:00pm
1 hour (actually 50 minutes)
Klaus 1116W
MIT Sloan Management
Over the past 30 years, researchers have developed successively faster algorithms for the maximum flow problem. The best strongly polynomial time algorithms have come very close to O(nm) time. Many researchers have conjectured that O(nm) time is the "true" worst case running time. We resolve the issue in two ways. First, we show how to solve the max flow problem in O(nm) time. Second, we show that the running time is even faster if m = O(n). In this case, the running time is O(n^2/log n).