Solving minimum-cost flow problems by successive approximation

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 01 Jan 1987Publisher:ACM PressJournal:Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87

Authors: Andrew V. Goldberg; Robert Endre Tarjan;

doi: 10.1145/28395.28397

Solving minimum-cost flow problems by successive approximation

- Summary
- Metrics

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(n3, n5/3 m2/3, nm log n) log (nC)) running time.

Related Organizations

Massachusetts Institute of Technology
United States
College of New Jersey
United States

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	101
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%