SOLVING MINIMUM-COST FLOW PROBLEMS BY SUCCESSIVE APPROXIMATION.

Andrew V. Goldberg, Robert E. Tarjan

Research output: Contribution to journalConference article

80 Scopus citations

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 languageEnglish (US)
Pages (from-to)7-18
Number of pages12
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'SOLVING MINIMUM-COST FLOW PROBLEMS BY SUCCESSIVE APPROXIMATION.'. Together they form a unique fingerprint.

  • Cite this