A Randomized Polynomial-Time Simplex Algorithm for Linear Programming

COMPUTER SCIENCE/DISCRETE MATH II
Topic:A Randomized Polynomial-Time Simplex Algorithm for Linear Programming
Speaker:Jonathan Kelner
Affiliation:Massachusetts Institute of Technology and Member, School of Mathematics
Date:Tuesday, October 3
Time/Room:10:30am - 12:30pm/S-101

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 may also discuss recent extensions of this result. 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.