On the complexity and approximability of budget-constrained minimum-cost flows

We investigate the complexity and approximability of the budget-constrained minimum cost flow problem, which is an extension of the traditional minimum cost flow problem by a second kind of costs associated with each arc, whose total value in a feasible flow is constrained by a given budget B. This problem appears both, in practical applications and as a subproblem when applying the epsilon-constraint method to the bicriteria minimum cost flow problem. We show that we can solve the problem exactly in weakly polynomial time O(log M . MCF(m, n, C, U)), where C, U, and M are upper bounds on the largest absolute cost, largest capacity, and largest absolute value of any number occurring in the input, respectively, and MCF(m, n, C, U) denotes the complexity of finding a traditional minimum cost flow. Moreover, we present two fully polynomial-time approximation schemes for the problem on general graphs and one with an improved running-time for the problem on acyclic graphs. (C) 2017 Elsevier B.V. All rights reserved.