An interior point method, based on rank-one updates, for linear programming

We propose a polynomial time primal-dual potential reduction algorithm for linear programming. Unlike any other interior point method, the new algorithm is based on a rank-one updating scheme for sequentially computing the projection matrices. For a standard linear programming problem, the number of operations required is [TeX: ${\\cal O}(mn)$] per main iteration and the overall computational complexity is [TeX: ${\\cal O}(mn^{2.5}L)$].