Minimum concave-cost network flow problems: Applications, complexity, and algorithms (Q2277131)

The paper is an overview of applications of minimum-cost network flow problems (MCNFP) economic problems and algorithms, a summary of known results in the complexity of the problem and some new results in the complexity area. At the end of the paper 108 references are given. Some of the applications are described in detail, others are just mentioned with further reference to the literature. The description of the algorithms is restricted to explaining the main ideas without going into details. The new complexity results are: (1) MCNFP is NP-hard if the objective function is strictly convex (even for bipartite networks), and (2) for capacitated MCNFP there is no pseudopolynomial algorithm in the sum of the arc capacities (unless \(P=NP\), of course).