Smoothed Analysis of Algorithms: Why the Simplex Algorithm
Usually Takes Polynomial Time
Shang-Hua Teng Boston University and
Akamai Technologies
Monday, October 3, 2005 10:00 a.m., 2310 CS
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 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.
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.
|