A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR PROGRAMMING-英文文献.pdf

COMBINATOR1CA4 (4) (1984) 373--395 A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR P R O G R A M M I N G N. K A R M A R K A R Received 20 August 1984 Revised 9 November 1984 We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requires O(tfSL) arithmetic operations on O(L) bit numbers, where n is the number of variables and L is the number of bits in the input. The running,time of this algorithm is better than the ellipsoid algorithm by a factor of O(n~~). We prove that given a polytope P and a strictly in- terior point a EP, there is a projective transformation of the space that maps P, a to P, a having the following property. The ratio of the radius of the smallest sphere with center a, containing P to the radius of the largest sphere with center a contained in P is O(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in poly- nomial time. 1. Informal outline In this Section we give an informal discussion of the main ideas involved in the algorithm. A more rigorous description will be given in the next Section. 1.1. Problem definition W e s h a l