**Authors: ** Narendra K Karmarkar**Published in: **Symposium On The Theory Of Computing

**Published in: **Combinatorica

**Year: **1984

**DOI: **10.1007/BF02579150

**Citations: **1427

**EI: ** NO

**Abstract: **

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: **