Genuinely Polynominal Simplex and Non-Simplex Algorithms for the Minimum Cost Flow Problem

We consider the minimum cost network flow problem min(cx: Ax=b, x> 0) on a graph G = (V,E). First we give a minor modification of Edmonds-Karp scaling technique, and we show that it solves the minimum cost flow problem in 0((IV1 2 log IVI)(IEI + IVi log VI)) steps. We also provide two dual simplex algorithms that solve the minimum cost flow problem in O(IV1 4 log IVi) pivots and O(IVi 3 log IVi) pivots respectively. Moreover, this latter dual simplex algorithm may be implemented so that the running time is proportional to that of Edmonds-Karp scaling technique