校 级 学 术 报 告
（运筹学讨论班）
报告人：堵丁柱 教授
(Department of Computer Science, University of Minnesota, U.S.A)
报告题目： Steiner Tree and its Approximation Solutions
地点：自然地理馆一楼报告厅
时间：2006年5月31（星期三）15:00-16:00
本讲座主要介绍堵丁柱教授解决的斯坦纳比难题及相关的近似算法。
贝尔实验室数学中心主任波雷克和研究员吉尔伯特对斯坦纳比问题作了许多研究，根据自己多年研究所得提出如下猜想：对欧氏平面上的任何有限点集，其最小的Steiner树同最小发生树的长度之比(称为Steiner比，即斯坦纳比)不小于√3/2。换言之，正三角形加点可以节省最多。
1990年堵丁柱教授在美国普林斯顿大学作访问学者，他和美国贝尔实验室黄光明研究员合作攻克了吉尔伯特--波雷克猜想，即斯坦纳比难题。正式公布以后，没想到会引起国际数学界那样广泛注意和强烈反响，被列为1989年-1990年度美国离散数学界和理论计算机科学界重大成果。英国大百科全书在收录这一成果时也评价说：“在过去的一年里，数学上最显著的进展包括长期、著名的猜想--一个最短网络的猜想……这个猜想就是斯坦纳比问题。”
堵丁柱（Du Dingzhu）教授1995年任美国Minnesota大学计算机科学系教授，现兼任美国自然科学基金计算机理论项目主任。堵丁柱教授1982年赴美国留学，1985年获美国加州大学数字专业博士学位，此后在美国Berkeley数字研究所从事博士后研究，1987年回国任中国科学院应用数学研究所研究员，堵丁柱长期从事算法与复杂性研究，先后获中国国家自然科学奖2项，他的Gilbert-Pollak猜测的证明曾在美国纽约时报、《Science》、《Science news》、SIAM新闻等媒体报导，被大英百科全书选为1991年六大数学杰出成就第1名。此外，堵丁柱曾获中国青年科学家奖、美国数学会主席Graham命名的Graham奖等。堵丁柱担任多种国际杂志及丛书主编和编委，作为会议主席等组织召开过13次国际会议，出版（主编）专著34本（套），发表学术论文137篇。


欢迎光临！