A polynomial time interior point algorithm for minimum cost flow problems

This paper deals with a minimum cost flow problem. The authors propose a polynomial time algorithm for the problem. The algorithm is based on an interior point algorithm for a general linear programming problem. Using some features of the minimum cost flow problem, the authors decrease the running time. They show that the algorithm requires at most O(ℝEℝ⁰’.⁵log(ℝVℝM)) iterations, O(ℝVℝ³) arithmetic operations in each iteration, and O(ℝVℝ⁰’.⁵ℝEℝ⁰’.⁵log(ℝVℝM)) arithmetic operations in total. Here ℝVℝ,ℝEℝ and M denote the number of nodes, that of arcs, and the maximum absolute value of input data, respectively.