Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The Simplex Method is the oldest and easiest algorithm in Linear Programming. Nevertheless, it puts the theory of computing in an awkward position. This is not a polynomial time algorithm (countrexamples are known), but in practice it runs in polynomial time. To theoretically explain the strange behavior, Spielman and Teng introduced the notion of the Smoothed Analysis of Algorithms. There, one "smoothes" an input by a small random perturbation, in hope that this models "most" practice problems. In this talk, we will do the smoothed analysis of the simplex algorithm. This brings up a variety of new problems in convex geometry.