| Title: | Spanning Trees with Low Stretch |
| Date: |
October 16, 2007 (Tuesday)
|
| Time: |
2:30 p.m. - 3:30 p.m.
|
| Venue: |
Room 121, 1/F, Ho Sin-hang Engineering Building,
The Chinese University of Hong Kong, Shatin, N.T. |
| Speaker: |
Professor Shang-Hua Teng
Department of Computer Science Boston University USA |
In 1991, Alon, Karp, Peleg, and West proved that every weighted connected graph G contains as a subgraph a spanning tree into which the edges of G can be embedded with average stretch exp [O (sqrt{log n loglog n}) ], and that there exists an n-vertex graph G such that all its spanning trees have average stretch Omega (log n).
We significantly reduce this exponential gap by constructing a spanning tree in G of average stretch O [(log n loglog n)^{2}]. Moreover, we show that this tree can be constructed in time O (m log^{2} n) in general, and in time O (m log n) if the input graph is unweighted. The main ingredient in our construction is a new graph decomposition technique.
Our new algorithm can be immediately used to improve the running time of the recent solver for diagonally dominant linear systems of Spielman and Teng from m exp{ (O (sqrt{log n loglog n}))} to m log^{O (1)}n, and to O (n (log n loglog n)^{2})) when the system is planar.
Applying a recent reduction of Boman, Hendrickson and?Vavasis, this provides an O (n (log n loglog n)^{2} time algorithm for solving the linear systems that arise when applying the finite element method to solve two-dimensional elliptic partial differential equations. Our result can also be used to improve several earlier approximation algorithms that use low-stretch spanning trees.
Joint work with Michael Elkin, Yuval Emek and Daniel Spielman.
BIOGRAPHY:
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 a B.S. degree in computer science and a B.A. degree in electrical engineering from Shanghai Jiao Tong University in 1985, a M.S. degree in computer science from University of Southern California (USC) in 1988, and a 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 the design and analysis of efficient algorithms. His recent interests include computational game theory, spectral graph theory and its applications in optimization and information processing, parallel scientific computing, computational geometry, graph partitioning and clustering, and cryptography. He has also received more than ten US Patents for his work on compiler optimization and Internet technology.
Enquiries: Miss Temmy So at tel 2609 8444
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar