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(n**3 ,n**5**/**3 m**2**/**3, nm log n) log(nC)) running time.
Original language | English (US) |
---|---|
Pages (from-to) | 7-18 |
Number of pages | 12 |
Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |
DOIs | |
State | Published - 1987 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software