A dual algorithm for submodular flow problems (Q1183393)

The authors propose a dual algorithm for the submodular flow problem. The concept of the `` best improving set'' is used to increase the dual objective as fast as possible, which is the kind of steepest ascent method employed by \textit{R. Hassin} [Math. Program. 25, 228-239 (1983; Zbl 0501.90035)] for the minimum cost flow problem. For the dual optimal solution thus obtained the associated submodular flow is constructed by complementary slackness.