EFFICIENT ALGORITHMS FOR MINIMUM-COST FLOW PROBLEMS WITH PIECEWISE-LINEAR CONVEX COSTS

We present two efficient algorithms for the minimum-cost flow problem in which are costs are piecewise-linear and convex. Our algorithms are based on novel algorithms of Orlin, which were developed for the case of linear are costs. Our first algorithm uses the Edmonds-Karp scaling technique. Its complexity is O(M log U(m + n log M)) for a network with n vertices, m arcs, M linear cost segments, and an upper bound U on the supplies and the capacities. The second algorithm is a strongly polynomial version of the first, and it uses Tardos's idea of contraction. Its complexity is O(M log M(m + n log M)). Both algorithms improve by a factor of at least Mim the complexity of directly applying existing algorithms to a transformed network in which are costs are linear.