- Series
- Other Talks
- Time
- Wednesday, May 23, 2012 - 1:00pm for 1 hour (actually 50 minutes)
- Location
- Klaus 1116W
- Speaker
- Jim Orlin – MIT Sloan Management
- Organizer
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).