Harvard Theory of Computation Seminar
A Randomized Polynomial-Time Simplex Algorithm for Linear Programming
Jonathan Adam Kelner, MIT
Place and Time: FRIDAY 2/24, Refreshments at 10:45, talk at 11. Maxwell Dworkin 319.
ABSTRACT
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 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 talk is on joint work with Daniel Spielman.