Article ID: | iaor1991316 |
Country: | United States |
Volume: | 15 |
Start Page Number: | 430 |
End Page Number: | 466 |
Publication Date: | Jun 1990 |
Journal: | Mathematics of Operations Research |
Authors: | Goldberg Andrew V., Tarjan Robert E. |
Keywords: | computational analysis |
The authors develop a new approach to solving minimum-cost circulation problems. The present approach combines methods for solving the maximum flow problem with successive approximation techniques based on cost scaling. The authors measure the accuracy of a solution by the amount that the complementary slackness conditions are violated. They propose a simple minimum-cost circulation algorithm, one version of which runs in O(