A new polynomial-time algorithm for linear programming |
| |
Authors: | N Karmarkar |
| |
Institution: | (1) AT&T Bell Laboratories, 07974 Murray Hill, NJ, U.S.A. |
| |
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.
This is a substantially revised version of the paper presented at the Symposium on Theory of Computing, Washington D. C.,
April 1984. |
| |
Keywords: | 90 C 05 |
本文献已被 SpringerLink 等数据库收录! |
|