Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time

October 6, 2004
2:45pm - 3:45 pm
Halligan 111


Theorists have long been challenged by the existence of remarkable algorithms that are known by scientists and engineers to work well in practice, but whose theoretical analyses have been are negative or unconvincing. The root of the problem is that algorithms are usually analyzed in one of two ways: by worst-case or average-case analysis. The former can improperly suggest that an algorithm will perform poorly, while the latter can be unconvincing because the random inputs it considers may fail to resemble those encountered in practice.

We introduce smoothed analysis to help explain the success of some of these algorithms and heuristics. Smoothed analysis is a hybrid of worst-case and average-case analyses that inherits advantages of both. The smoothed complexity of an algorithm is the maximum over its inputs of the expected running time of the algorithm under slight random perturbations of that input, measured as a function of both the input length and the magnitude of the perturbations. If an algorithm has low smoothed complexity, then it should perform well on most inputs in every neighborhood of inputs.

In this talk, we will explain how smoothed analysis can help explain the excellent observed behavior of the simplex method, Gaussian elimination, and interior point methods. In particular, we show that the simplex algorithm has polynomial smoothed complexity. The simplex algorithm is the classic example of an algorithm that performs well in practice but takes exponential time in the worst case.

This is joint work with Daniel Spielman of MIT


Short Bio: Shang-Hua Teng is now a full professor in the Computer Science Department at Boston University and also a senior research scientist at Akamai Technologies Inc. He taught as a faculty in the Department of Mathematics of MIT and in the Computer Science Departments of the University of Minnesota and UIUC. He has worked and consulted for IBM Almaden Research Center, Intel Corporation, Xerox PARC, Cray Research/SGI, Thinking Machine Corporation, and NASA Ames Research Center. He is an Alfred P. Sloan Fellow, winner of Senior Xerox Award for Outstanding Faculty Research (UIUC), and has received NSF Faculty Early Career Development Award.

Teng received the B.S. degree in computer science and the B.A. degree in electrical engineering from Shanghai Jiao Tong University in 1985, the M.S. degree in computer science from University of Southern California (USC) in 1988, and the Ph.D. degree in computer science from Carnegie Mellon University (CMU) in 1991.

With Dan Spielman of MIT, he developed the theory of Smoothed Analysis for modeling and analyzing practical algorithms, and had demonstrated that the simplex method for linear programming has a polynomial smoothed complexity. This joint work was cited by National Science Foundation in its FY'03 budget request to Congress. His research centers on efficient algorithm design and implementation. His recent interests include spectral techniques for optimization and information processing, parallel scientific computing, computational geometry, VLSI and circuit simulation, combinatorial optimization and probabilistic analysis, distributed computing and cryptography. He has also received 7 US Patents for his work on compiler optimization and Internet technology.