Solving Minimum-Cost Flow Problems by Successive Approximation
Report ID: TR-081-87Author: Tarjan, Robert E. / Goldberg, Andrew V.
Date: 1987-02-00
Pages: 13
Download Formats: |PDF|
Abstract:
We introduce a framework for solving minimum-cost flow problems. Our approach measures the quality of a solution by the amount that the complementary slackness conditions are violated. We show how to extend techniques developed for the maximum flow problem to improve the quality of a solution. This framework allows us to achieve O(min(n3, n5/3m2/3, nm log n)log(nC)) running time.