A New Polynomial-Time Algorithm for Linear Programming

We present a new polynomial-time algorithm for linear programming. The running-time of this algorithm is O ( n 3-5 L 2 ), as compared to O ( n 6 L 2 ) for the ellipsoid algorithm. We prove that given a polytope P and a strictly interior point a ε P , 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 polynomial-time.

Authors

• Narendra Karmarkar

Keywords

No keywords are indexed for this paper.