Finding minimum-cost flows by double scaling

Ravindra K. Ahuja, Andrew V. Goldberg, James B. Orlin, Robert E. Tarjan

Research output: Contribution to journalArticle

45 Scopus citations

Abstract

Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in O(nm(log log U) log(nC)) time on networks with n vertices, m edges, maximum arc capacity U, and maximum arc cost magnitude C. The major techniques used are the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja and Orlin, the cost-scaling approach of Goldberg and Tarjan, and the dynamic tree data structure of Sleator and Tarjan. For nonsparse graphs with large maximum arc capacity, we obtain a similar but slightly better bound. We also obtain a slightly better bound for the (noncapacitated) transportation problem. In addition, we discuss a capacity-bounding approach to the minimum-cost flow problem.

Original languageEnglish (US)
Pages (from-to)243-266
Number of pages24
JournalMathematical Programming
Volume53
Issue number1-3
DOIs
StatePublished - Jan 1 1992

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Minimum-cost flows
  • dynamic trees
  • minimum-cost circulations
  • scaling
  • transportation problem

Fingerprint Dive into the research topics of 'Finding minimum-cost flows by double scaling'. Together they form a unique fingerprint.

  • Cite this