Finding Minimum-Cost Circulations by Successive Approximation

TLDR

The authors introduce a novel approach to solve minimum‑cost circulation problems. By combining maximum‑flow techniques with cost‑scaling successive approximation, the authors present a simple algorithm that runs in \(O(n^3\log(nC))\) time (improved to \(O(nm\log(n^2/m)\log(nC))\)) and a parallel version with \(O(n^2(\log n)\log(nC))\) time via a sequence of blocking flow problems. The approach delivers strongly polynomial minimum‑cost circulation algorithms, suggests the problem is comparable in difficulty to maximum flow, and is expected to perform exceptionally well in practice.

Abstract

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(n 3 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(n 2 /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(n 2 (log n)log(nC))-time, m-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.