This paper discusses a new polynomial time algorithm for linear programming (LP). It is an interior point method whose worst case computational complexity is $0(n\sp{3.5}L)$ arithmetic operations on 0(L) bit numbers, where n is the number of variables and L is the number of bits in the input. The complexity bound for this algorithm is better than that for the ellipsoid algorithm by a factor of $0(n\sp{2.5}).$
The author shows that every LP can be transformed into the form: min cx subject to $x\in \Omega \cap \Delta$, where $\Omega$ is the subspace $\{$ $x: Ax=0\}$ and $\Delta$ is the simplex $\{$ $x: x\ge 0$ and $\Sigma x\sb j=1\}$, and the minimum objective value in the problem is known to be zero. His algorithm solves the LP in this form.
Let $a\sb 0=(1/n)e$, where e is the vector of all 1’s in $R\sp n$. Let $B(a\sb 0,r)$, $B(a\sb 0,R)$ be respectively the largest sphere with center $a\sb 0$ lying in $\Delta$, and the smallest sphere with center $a\sb 0$ containing $\Delta$. Then $R/r=(n-1)$. Using this he shows that if $a\sb 0$ is feasible, $a\sb 0-r\hat c$, where $\hat c$ is the normalized vector which in the orthogonal projection of c in $\Omega$, is chosen to the minimum objective value by a factor of (1-1/(n-1)). This is the main result on which the algorithm is based.
The algorithm is initiated with a feasible solution $x\sp 0>0$, and it generates a descent sequence of positive feasible points $x\sp 0,x\sp 1,..$.. In the kth step, the point $x\sp k$ is brought into the center of the simplex by a projective transformation, a step of the form described above is taken, and the inverse projective transformation is applied, leading to the next point $x\sp{k+1}$, reducing the objective function value by a factor of 0(n). The sequence of points generated, converges to a near optimal solution in polynomial time.