Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs

Abstract

We present two efficient algorithms for the minimum-cost flow problem in which arc costs are piecewise-linear and convex. Our algorithms are based on novel algorithms of Orlin, which were developed for the case of linear arc costs. Our first algorithm uses the Edmonds-Karp scaling technique. Its complexity isO(M logU(m+n logM)) for a network withn vertices,m arcs, M linear cost segments, and an upper boundU 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 isO(M logM(m+n logM)). Both algorithms improve by a factor of at leastM/m the complexity of directly applying existing algorithms to a transformed network in which arc costs are linear.