A Randomized Polynomial-time Simplex Algorithm for Linear Programming
Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, стр. 51--60. New York, NY, USA, ACM, (2006)DOI: 10.1145/1132516.1132524
Аннотация
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.
