Our office is just a block away from MIT. That's nice, because I can go to the library and seminars. The most interesting seminar I went to at MIT this year was probably one on a polynomial time simplex algorithm for linear programming:
Algorithms and Complexity Spring 2006
A Randomized Polynomial-Time Simplex Algorithm for Linear Programming
Speaker: Jonathan A. KelnerIn 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.
There have been polynomial time interior point algorithms for solving LP's, but variants of the simplex algorithm have always had exponential time in the worst case. (Those damn Klee-Minty Cubes...) It has been an open problem for decades. Now he just needs to make it strongly polynomial.
It was one of those seminars that you don't really follow, but it sure seems important. He defended this thesis this week, so contratulations to Jon. I'm sure he'll get a nice academic post.
His website, with papers and such is here.
Comments