EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
100. From Incremental Transitive Closure to Strongly Polynomial Maximum Flow
Invited abstract in session MD-26: Optimization problems on graphs, stream Combinatorial Optimization.
Monday, 14:30-16:00Room: 012 (building: 208)
Authors (first author is the speaker)
| 1. | James Orlin
|
| ORC and Sloan School of Management, MIT | |
| 2. | Daniel Dadush
|
| Networks & Optimization, CWI | |
| 3. | Aaron Sidford
|
| Departments of Computer Science and MS&E, Stanford University | |
| 4. | Laszlo Vegh
|
| Mathematics, LSE |
Abstract
The best strongly polynomial bound for maximum flows in a graph with n nodes and m arcs is the O(nm) bound by Orlin (STOC 2013). His algorithm runs in O(nm) time for graphs that are suitable sparse. King, Rao, and Tarjan (J. Algorithms 1994) had already established the O(nm) run time for all other networks.
Strengthening Orlin's approach, we present a black-box framework that makes any weakly polynomial maximum flow algorithms to strongly polynomial. The algorithm relies on using Italiano’s data structure for maintaining an incremental dynamic transitive closure, which runs in O(nm) time. Surprisingly, the remaining operations take much less time, except in the most dense networks. If one can improve the run time for dynamic transitive closure, then one can speed up the running time for the max flow problem as well. We also obtain improved running times for a range of special cases including instances with a bounded number of arcs with finite upper capacity and instances with bounded tree depth.
Keywords
- Network Flows
- Algorithms
- Combinatorial Optimization
Status: accepted
Back to the list of papers