题目：Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually

Takes Polynomial Time

报告人：滕尚华（Shang-Hua Teng）教授

单位：Boston University/Akamai Technologies

时间：2004年5月27日下午2：30

地点：清华大学西主楼1区4层406

（智能技术与系统国家重点实验室）

摘要： 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

报告人简介： 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 a US Patent for

his work on a compiler optimization technology.