Algorithms and Complexity Seminar
Thursday, May 4, 2006, 4-5:15pm in 32-G575.
A Randomized Polynomial-Time Simplex Algorithm for Linear
Programming
Jon Kelner (MIT)
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 is
joint work with Daniel Spielman.
If time permits, I will also discuss recent extensions of this result
with Evdokia Nikolova. Using tools from random matrix theory, we
extend the technical tools from the above work to provide a smoothed
analysis of an algorithm to solve a wide class of non-convex
optimization problems.
Host: Madhu Sudan