On the flow cost lowering problem

This paper presents the flow cost lowering problem (FCLP), which is an extension to the integral version of the well-known minimum cost flow problem (MCFP). While in the MCFP the flow costs are fixed, the FCLP admits lowering the flow cost on each arc by upgrading the arc. Given a flow value and a bound on the total budget which can be used for upgrading the arcs, the goal is to find an upgrade strategy and a flow of minimum cost. The FCLP is shown to be NP-hard even on series–parallel graphs. On the other hand the paper provides a polynomial time approximation algorithm on series–parallel graphs.