SOME RECENT ADVANCES IN NETWORK FLOWS

The literature on network flow problems is extensive, and over the past 40 years researchers have made continuous improvements to algorithms for solving several classes of problems. However, the surge of activity concerning the algorithmic aspects of network flow problems over the past few years has been particularly striking. Several techniques have proven to be very successful in permitting researchers to make these recent contributions: (i) scaling of the problem data; (ii) improved analysis of algorithms, especially amortized worst-case performance and the use of potential functions; and (iii) enhanced data structures. This survey illustrates some of these techniques and their usefulness in developing faster network flow algorithms. The discussion focuses on the design of faster algorithms from the worst-case perspective, and is limited to the following fundamental problems: the shortest path problem, the maximum flow problem, and the minimum cost flow problem. Several representative algorithms from each problem class are considered, including the radix heap algorithm for the shortest path problem, preflow push algorithms for the maximum flow problem, and the pseudoflow push algorithms for the minimum cost flow problem.