A Polynomial-Time Parametric Simplex Algorithm for the Minumum Cost Network Flow Problem

In this paper we consider the minimum cost network flow problem: min(cx: Ax = b, x 0), where A is an m x n vertex-edge incidence matrix. We show how to solve this problem as a parametric linear program with 0(m b*) pivots, where b * is the number of l's in the binary representation of b. The parametric formulation is non-linear and is based on Edmonds-Karp scaling technique. sai·igrs31--l a ____ In this paper we consider the minimum cost network flow problem (1). Minimize cx Subject to Ax = b (1) x 0, where A is a full row'rank m x n matrix in which there is at most one 1 and at most one-1 in each column and the remaining entries are all 0. Moreover, b is an integral m-vector, and c is a real n-vector