A new polynomial-time algorithm for linear programming

ABSTRACT

We present a new polynomial-time algorithm for linear programming. The running-time of this algorithm is O(n3-5L2), as compared to O(n6L2) for the ellipsoid algorithm. We prove that given a polytope P and a strictly interior point a &egr; 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.

REFERENCES

• 1: 1. V. Klee and G. L. Minty, "How good is the simplex algorithm?" in O. Shisha (ed.) Inequalities III, Academic Press, New York, 1972, p. 159-179.
• 2: 2. L. G. Khachiyan, "A polynomial Algorithm in Linear Programming," Doklady Akademiia Nauk SSSR 244:S (1979), p. 1093-1096, translated in Soviet Mathematics Doklady 20:1 (1979), p. 191-194.
• 3: 3. M. Grotschel, L. Lovasz, A. Schrijver, Then Elipsoid Method and its Consequences in Combinatorial Optimization, Combinatorica 1 (2) 1981, p. 169-197.
• 4: 4. Dantzig, G. B., Linear Programming and Extensions, Princeton University Press, Princeton, NJ (1963).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Performance, Theory