Answers are grounded in this paper and cite their sources.
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 Ο(min(n3, n5/3 m2/3, nm log n) log (nC)) running time.
No takes yet. Share an insight, caveat, or question.
Goldberg et al. (1987) studied this question.