SOLVING MINIMUM-COST FLOW PROBLEMS BY SUCCESSIVE APPROXIMATION.

Andrew V. Goldberg; Robert E. Tarjan

doi:10.1145/28395.28397

SOLVING MINIMUM-COST FLOW PROBLEMS BY SUCCESSIVE APPROXIMATION.

Andrew V. Goldberg, Robert E. Tarjan

Research output: Contribution to journal › Conference article › peer-review

105 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 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	https://doi.org/10.1145/28395.28397
State	Published - 1987
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/28395.28397

Cite this

@article{16808153a3994dc9bae95076d109540a,

title = "SOLVING MINIMUM-COST FLOW PROBLEMS BY SUCCESSIVE APPROXIMATION.",

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.",

author = "Goldberg, \{Andrew V.\} and Tarjan, \{Robert E.\}",

year = "1987",

doi = "10.1145/28395.28397",

language = "English (US)",

pages = "7--18",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - SOLVING MINIMUM-COST FLOW PROBLEMS BY SUCCESSIVE APPROXIMATION.

AU - Goldberg, Andrew V.

AU - Tarjan, Robert E.

PY - 1987

Y1 - 1987

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0023606704

UR - https://www.scopus.com/inward/citedby.url?scp=0023606704&partnerID=8YFLogxK

U2 - 10.1145/28395.28397

DO - 10.1145/28395.28397

M3 - Conference article

AN - SCOPUS:0023606704

SN - 0734-9025

SP - 7

EP - 18

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

ER -

SOLVING MINIMUM-COST FLOW PROBLEMS BY SUCCESSIVE APPROXIMATION.

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this