A new polynomial-time algorithm for linear programming
A new polynomial-time algorithm for linear programming
复制标题
DOI：
10.1145/800057.808695
复制
发表时间：
1984-12
期刊：
影响因子：
1.1
通讯作者：
N. Karmarkar
中科院分区：
文献类型：
--
作者：
N. Karmarkar
提出了一种新的线性规划多项式时间算法。在最坏的情况下，该算法需要对O（L）位数进行O（n3.5L）次算术运算，其中n是变量数，L是输入中的位数。该算法的运行时间是椭球算法的O（n2.5）倍。证明了给定一个多面体P和一个严格内点a εP，存在一个映射P，a到P ′，a′的射影变换，该射影变换具有下列性质.以a′为圆心的包含P ′的最小球面的半径与以a′为圆心的包含P ′的最大球面的半径之比为O（n）。该算法包括重复应用这样的投影变换，每个优化后的内接球，以创建一个序列的点，在多项式时间收敛到最优解。
We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n3.5L) 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(n2.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.