Finding Minimum-Cost Circulations by Successive Approximation.
Abstract
We develop a new approach to solving minimum cost circulation problems. Our approach combines methods for solving the maximum flow problems 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(n3log(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(nmlog(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(nlog(nC)) blocking flow problems. A corollary of this result is an O(n2(logn)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. Keywords: Network flows, Minimum cost flow, Combinatorial optimization.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1987
- Accession Number
- ADA192724
Entities
People
- Andrew V. Goldberg
- Robert Tarjan
Organizations
- Massachusetts Institute of Technology