Linear approximations in a dynamic programming approach for the uncapacitated single-source minimum concave cost network flow problem in acyclic networks

We consider minimum concave cost flow problems in acyclic, uncapacitated ne tworks with a single source. For these problems a dynamic programming schem e is developed. It is shown that the concave cost functions on the arcs can be approximated by linear functions. Thus the considered problem can be so lved by a series of linear programs. This approximation method, whose conve rgence is shown, works particularly well, if the nodes of the network have small degrees. Computational results on several classes of networks are rep orted.