In this paper, we consider a modified version of a well-known long-step primal-dual infeasible IP algorithm for solving the linear program $\min\{c^T x : Ax=b, \, x \ge 0\}$, $A \in \Re^{m \times n}$, where the search directions are computed by means of an iterative linear solver applied to a preconditioned normal system of equations. We show that the number of (inner) iterations of the iterative linear solver at each (outer) iteration of the algorithm is bounded by a polynomial in $m$, $n$ and a certain condition number associated with $A$, while the number of outer iterations is bounded by $\O(n^2 \log \epsilon^{-1} )$, where $\epsilon$ is a given relative accuracy level. As a special case, it follows that the total number of inner iterations is polynomial in $m$ and $n$ for the minimum cost network flow problem.
Citation
Manuscript, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, October 2003.