A fast cost scaling algorithm for submodular flow

This paper presents the current fastest known weakly polynomial algorithm f or the submodular how problem when the costs are not too big. It combines R ock's or Bland and Jensen's cost scaling algorithms, Cunningham and Frank's primal-dual algorithm for submodular flow, and Fujishige and Zhang's push/ relabel algorithm for submodular maximum flow to get a running time of O(n( 4)h log C), where n is the number of nodes, C is the largest absolute value of are costs and h is the time for computing an exchange capacity in an in stance of this problem. O 2000 Elsevier Science B.V. All rights reserved.