This paper discusses a new polynomial time algorithm for linear programming (LP). It is an interior point method whose worst case computational complexity is 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
The author shows that every LP can be transformed into the form: min cx subject to , where is the subspace and is the simplex and , and the minimum objective value in the problem is known to be zero. His algorithm solves the LP in this form.
Let , where e is the vector of all 1’s in . Let , be respectively the largest sphere with center lying in , and the smallest sphere with center containing . Then . Using this he shows that if is feasible, , where is the normalized vector which in the orthogonal projection of c in , 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 , and it generates a descent sequence of positive feasible points .. In the kth step, the point 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 , 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.