THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS
THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS
复制标题
DOI：
10.1145/321694.321699
复制
发表时间：
1972-01-01
影响因子：
2.5
通讯作者：
KARP, RM
中科院分区：
文献类型：
--
作者：
EDMONDS, J;KARP, RM
本文提出了求解最大流问题、希区柯克运输问题和一般最小费用流问题的新算法。在这些算法中的步骤的数量上界的推导，并示出compale有利的步骤的数量上界所需的早期算法。本文首先阐述了最大流问题，给出了求解该问题的Ford-Fulkerson标号法，并指出不恰当地选择增流路径会导致严重的计算困难。然后给出了避免这些困难的选择规则。我们证明了，如果每一次流扩充都是沿着一条具有最少弧数的扩充路径进行的，则在n个节点网络中，经过不超过~（na-n）次的扩充后，将获得最大流;然后，我们表明，如果选择每个流量变化以产生流量值的最大增加，那么，假设容量是整数，如果f *（t，S）增大，则最大流量将在至多1+ logM/（M-1）内确定，其中f *（t，s）是最大流量的值，M是穿过切口的弧的最大数目。接下来给出了最小费用流问题的一种新算法，其中所有最短路径计算都在所有权重非负的网络上执行。特别地，该算法在O（n3）步内解决了n × n分配问题.接下来，我们探讨了一个“缩放”技术解决最小成本流的问题，通过处理一系列派生的问题与“按比例缩小”的能力。结果表明，用这种方法求解具有m个源和n个汇，m~ n和最大流量B的Liitchcock输运问题，至多需要（n+ 2）log ~ 2（B/n）个流量增量。类似的结果也给出了一般的最小费用流problem. A摘要说明本文件的主要结果是在卡尔加里国际会议组合结构及其应用，1969年6月。在l）inic（1970）的一篇论文中，得到了一个与1.2节的主要结果密切相关的结果。Dinic表明，在一个网络与n个节点和p弧，最大流量可以计算在0（n2 p）原始操作的算法，增加沿着最短的增广路径。
This paper presents new algorithms for the maximum flow problem, the Hitchcock transportation problem, and the general minimum-cost flow problem. Upper bounds on the numbers of steps in these algorithms are derived, and are shown to compale favorably with upper bounds on the numbers of steps required by earlier algorithms. First, the paper states the maximum flow problem, gives the Ford-Fulkerson labeling method for its solution, and points out that an improper choice of flow augmenting paths can lead to severe computational difficulties. Then rules of choice that avoid these difficulties are given. We show that, if each flow augmentation is made along an augmenting path having a minimum number of arcs, then a maximum flow in an n-node network will be obtained after no more than~(na-n) augmentations; and then we show that if each flow change is chosen to produce a maximum increase in the flow value then, provided the capacities are integral, a maximum flow will be determined within at most 1+ logM/(M--1) if (t, S) augmentations, wheref*(t, s) is the value of the maximum flow and M is the maximum number of arcs across a cut. Next a new algorithm is given for the minimum-cost flow problem, in which all shortest-path computations are performed on networks with all weights nonnegative. In particular, this algorithm solves the n X n assigmnent problem in O (n 3) steps. Following that we explore a" scaling" technique for solving a minimum-cost flow problem by treating a sequence of derived problems with" scaled down" capacities. It is shown that, using this technique, the solution of a Iiitchcock transportation problem with m sources and n sinks, m~ n, and maximum flow B, requires at most (n+ 2) log2 (B/n) flow augmentations. Similar results are also given for the general minimum-cost flow problem.An abstract stating the main results of the present paper was presented at the Calgary International Conference on Combinatorial Structures and Their Applications, June 1969. In a paper by l) inic (1970) a result closely related to the main result of Section 1.2 is obtained. Dinic shows that, in a network with n nodes and p arcs, a maximum flow can be computed in 0 (n2p) primitive operations by an algorithm which augments along shortest augmenting paths.