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

Theorists have been challenged by the existence of remarkable algorithms that are known by scientists and engineers to work well in practice, but whose theoretical analyses are negative or inconclusive. 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 overly optimistic because the random inputs it considers can bear little resemblance to those encountered in practice. We propose an analysis that we call smoothed analysis that can help explain the success of many algorithms that both worst-case and average-case cannot. In smoothed analysis, we measure the performance of an algorithm under slight random perturbations of arbitrary inputs. In particular, we consider Gaussian perturbations of inputs to algorithms that take real and complex inputs, and we measure the running time of algorithms in terms of the input size and the variance of the perturbations. 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. In the 1980's the simplex algorithm was shown to converge in expected polynomial time on various distributions of random inputs, most notably by Borgwardt and Smale. However, the last 20 years of research in probability and numerical analysis have taught us that these random instances have very special properties that one should not expect to find in practice.
For every matrix A with entries of absolute value at most 1, every vector c, and every vector b whose entries are 1 or -1, we show that the simplex algorithm using the shadow-vertex pivot rule takes expected time polynomial in 1/σ and the sizes of A and c to solve:
minimize c'x
s.t (A + σ G) x ≤ b
If A is well-scaled, then the solution to this program is an approximation to the original.
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 Departemnt 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 and covered by Technology Review (June 2003).
His research centers on effecient 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 seven US Patents for his work on compiler optimization and Internet technologies.