A New Polynomial-time Algorithm For Linear Programming

Basic infomation
Authors: Narendra K Karmarkar
Published in: Symposium On The Theory Of Computing
Published in: Combinatorica
Year: 1984   
DOI: 10.1007/BF02579150
Citations: 1427
abstract we present a new polynomial time algorithm for linear programming in the worst case , the algorithm requireso \( n 3 5 l \) arithmetic operations ono \( l \) bit numbers , wheren is the number of variables andl is the number of bits in the input the running time of this algorithm is better than the ellipsoid algorithm by a factor ofo \( n 2 5 \) we prove that given a polytopep and a strictly interior point a \? p , there is a projective transformation of the space that mapsp , a top \? , a \? having the following property the ratio of the radius of the smallest sphere with center a \? , containingp \? to the radius of the largest sphere with center a \? contained inp \? iso \( 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 polynomial time
Popular Words:
Cited By