A Randomized Polynomial-Time Simplex Algorithm for Linear Programming

In this talk, I shall 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.

This talk is on joint work with Daniel Spielman.