A Randomized Polynomial-Time Simplex Algorithm for Linear Programming
by Daniel A. Spielman
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 leq 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.
This is joint work with Jonathan Kelner.