Published on *Computer Science Department at Princeton University* (https://www.cs.princeton.edu)

We develop a new approach to solving minimum-cost circulation problems. Our approach combines methods for solving the maximum flow problem with successive approximation techniques based on cost scaling. We measure the accuracy of a solution by the amount that the complementary slackness conditions are violated. We propose a simple minimum-cost circulation algorithm, one version of

which runs in O(n3 log(nC)) time on an n-vertex network with integer arc costs of absolute value at most C. By incorporating sophisticated data structures into the algorithm, we obtain a time bound of O(nm log(n2/m) log(nC))on a network with m arcs. A slightly different use of our approach shows that a minimum-cost circulation can be computed by solving a sequence of O(n log(nC)) blocking flow problems. A corollary of this result is an O(n2(log n) log(nC))-time, n-processor parallel minimum-cost circulation algorithm. Our approach also yields strongly polynomial minimum-cost circulation algorithms. Our results provide evidence that the minimum-cost circulation problem is not much harder than the maximum flow problem. We believe that a suitable implementation of our method will perform extremely well in practice.

**Links**

[1] https://www.cs.princeton.edu/research/techreps/author/412

[2] https://www.cs.princeton.edu/research/techreps/author/384

[3] ftp://ftp.cs.princeton.edu/techreports/1987/106.pdf