A randomized polynomial-time simplex algorithm for linear programming

ABSTRACT

We present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input.We begin by reducing the input linear program to a special form in which we merely need to certify boundedness. As boundedness does not depend upon the right-hand-side vector, we run the shadow-vertex simplex method with a random right-hand-side vector. Thus, we do not need to bound the diameter of the original polytope.Our analysis rests on a geometric statement of independent interest: given a polytope A x ≤ b in isotropic position, if one makes a polynomially small perturbation to b then the number of edges of the projection of the perturbed polytope onto a random 2-dimensional subspace is expected to be polynomial.

REFERENCES

• 1: Dimitris Bertsimas , Santosh Vempala, Solving convex programs by random walks, Journal of the ACM (JACM), v.51 n.4, p.540-556, July 2004 [doi>10.1145/1008731.1008733]
• 2: K. H. Borgwardt. The Simplex Method: a probabilistic analysis. Number 1 in Algorithms and Combinatorics. Springer-Verlag, 1980.
• 3: G. B. Dantzig. Maximization of linear function of variables subject to linear inequalities. In T. C. Koopmans, editor, Activity Analysis of Production and Allocation, pages 339--347. 1951.
• 4: G. B. Dantzig. Linear Programming and Extensions. Princeton University Press, 1963.
• 5: Amit Deshpande , Daniel A. Spielman, Improved Smoothed Analysis of the Shadow Vertex Simplex Method, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.349-356, October 23-25, 2005 [doi>10.1109/SFCS.2005.44]
• 6: John Dunagan , Santosh Vempala, A simple polynomial-time rescaling algorithm for solving linear programs, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007404]
• 7: Komei Fukuda , Tamás Terlaky, Criss-cross methods: a fresh view on pivot algorithms, Mathematical Programming: Series A and B, v.79 n.1-3, p.369-395, Oct. 1, 1997 [doi>10.1007/BF02614325]
• 8: S. Gass and T. Saaty. The computational algorithm for the parametric objective function. Naval Research Logistics Quarterly, 2:39--45, 1955.
• 9: M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1991.
• 10: G. Kalai and D. J. Kleitman. A quasi-polynomial bound for the diameter of graphs of polyhedra. Bulletin Amer. Math. Soc., 26:315--316, 1992.
• 11: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 12: L. G. Khachiyan. A polynomial algorithm in linear programming. Doklady Akademia Nauk SSSR, pages 1093--1096, 1979.
• 13: N. Megiddo and R. Chandrasekaran. On the epsilon-perturbation method for avoiding degeneracy. Operations Research Letters, 8:305--308, 1989.
• 14: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 15: Daniel A. Spielman , Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM), v.51 n.3, p.385-463, May 2004 [doi>10.1145/990308.990310]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory