Computing Maximum Flow with Augmenting Electrical Flows
Computing Maximum Flow with Augmenting Electrical Flows
复制标题
通过增强电流计算最大流量
DOI：
10.1109/focs.2016.70
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Madry
中科院分区：
文献类型：
--
作者：
A. Madry
本文对具有m条弧和最大整数容量U的有向图的最大s-t流问题（和最小s-t割问题）提出了一个O时间（m7/10 U1/7）算法。这与Madry [30]在单位容量情况下的O（mU）10/7）时间算法的运行时间相匹配，并且在U适度大并且图足够稀疏时，它以及Lee和Sidford [25]的O（mU）log U）时间算法都有所改进。通过众所周知的减少，这也意味着类似的运行时间改善的最大基数二分b匹配问题。我们的算法的优点之一是它比[30]和[25]中提出的算法简单得多。特别是，这些算法采用了一个复杂的边界点方法框架，而我们的算法是直接投在经典的增广路径设置，几乎所有的组合最大流算法使用。在一个高层次上，所提出的算法采用原始对偶方法，其中每次迭代使用电流计算来找到当前残差图中的增强S-T流并更新对偶解。我们表明，通过保持一定的谨慎耦合这些原始和对偶的解决方案，我们总是保证取得重大进展。
We present an Õ (m 7/10 U 1/7)-time algorithm for the maximum s-t flow problem (and the minimum s-t cut problem) in directed graphs with m arcs and largest integer capacity U. This matches the running time of the Õ (mU)10/7)- time algorithm of Madry [30] in the unit-capacity case, and improves over it, as well as over the Õ (m√n log U)-time algorithm of Lee and Sidford [25], whenever U is moderately large and the graph is sufficiently sparse. By well-known reductions, this also implies similar running time improvements for the maximum-cardinality bipartite b-matching problem. One of the advantages of our algorithm is that it is significantly simpler than the ones presented in [30] and [25]. In particular, these algorithms employ a sophisticated interior-point method framework, while our algorithm is cast directly in the classic augmenting path setting that almost all the combinatorial maximum flow algorithms use. At a high level, the presented algorithm takes a primal dual approach in which each iteration uses electrical flows computations both to find an augmenting s-t flow in the current residual graph and to update the dual solution. We show that by maintain certain careful coupling of these primal and dual solutions we are always guaranteed to make significant progress.