This paper presents new algorithms for the maximum flow problem, the Hitchcock transportation problem, and the general minimum-cost flow problem. It provides upper bounds on the number of steps required by these algorithms, showing that they are efficient compared to earlier methods.
The paper first discusses the maximum flow problem, introducing the Ford-Fulkerson labeling method. It highlights that improper selection of flow augmenting paths can lead to computational difficulties. The paper then presents rules to avoid these issues, showing that using augmenting paths with the minimum number of arcs can lead to a maximum flow in an n-node network after no more than (n³ - n)/n augmentations. It also shows that if each flow change is chosen to maximize the increase in flow value, then a maximum flow can be determined within at most 1 + log_M(M,1) f*(t,s) augmentations, where f*(t,s) is the maximum flow value and M is the maximum number of arcs across a cut.
Next, the paper introduces a new algorithm for the minimum-cost flow problem, where all shortest-path computations are performed on networks with nonnegative weights. This algorithm solves the n×n assignment problem in O(n³) steps. It then explores a "scaling" technique for solving the minimum-cost flow problem by treating a sequence of derived problems with scaled-down capacities. It shows that the solution of a Hitchcock transportation problem with m sources and n sinks requires at most (n + 2) log₂(B/n) flow augmentations, where B is the maximum flow. Similar results are given for the general minimum-cost flow problem.
The paper also discusses a scaling method for the minimum-cost flow problem, which involves solving a sequence of problems with scaled-down capacities. This method reduces the number of flow augmentations required, making it more efficient than previous methods. The scaling method is shown to be effective for both the Hitchcock transportation problem and the general minimum-cost flow problem, with the number of flow augmentations depending logarithmically on the capacities rather than linearly. The paper concludes with a discussion of the efficiency of the scaling method and its implications for solving minimum-cost flow problems.This paper presents new algorithms for the maximum flow problem, the Hitchcock transportation problem, and the general minimum-cost flow problem. It provides upper bounds on the number of steps required by these algorithms, showing that they are efficient compared to earlier methods.
The paper first discusses the maximum flow problem, introducing the Ford-Fulkerson labeling method. It highlights that improper selection of flow augmenting paths can lead to computational difficulties. The paper then presents rules to avoid these issues, showing that using augmenting paths with the minimum number of arcs can lead to a maximum flow in an n-node network after no more than (n³ - n)/n augmentations. It also shows that if each flow change is chosen to maximize the increase in flow value, then a maximum flow can be determined within at most 1 + log_M(M,1) f*(t,s) augmentations, where f*(t,s) is the maximum flow value and M is the maximum number of arcs across a cut.
Next, the paper introduces a new algorithm for the minimum-cost flow problem, where all shortest-path computations are performed on networks with nonnegative weights. This algorithm solves the n×n assignment problem in O(n³) steps. It then explores a "scaling" technique for solving the minimum-cost flow problem by treating a sequence of derived problems with scaled-down capacities. It shows that the solution of a Hitchcock transportation problem with m sources and n sinks requires at most (n + 2) log₂(B/n) flow augmentations, where B is the maximum flow. Similar results are given for the general minimum-cost flow problem.
The paper also discusses a scaling method for the minimum-cost flow problem, which involves solving a sequence of problems with scaled-down capacities. This method reduces the number of flow augmentations required, making it more efficient than previous methods. The scaling method is shown to be effective for both the Hitchcock transportation problem and the general minimum-cost flow problem, with the number of flow augmentations depending logarithmically on the capacities rather than linearly. The paper concludes with a discussion of the efficiency of the scaling method and its implications for solving minimum-cost flow problems.