从7月7日开始，应中国科学院大学数学科学学院邀请，美国德克萨斯大学计算机系教授堵丁柱在怀柔校区教学楼1-209教室开设了为期20学时的夏季学期课程《近似算法的分析与设计》。
此次课程主要由以下6部分组成：（1）算法的相关知识：引入P、NP的概念，以顶点覆盖、背包问题为例讲解了如何估计一些经典的NP完备问题的近似比。（2）贪婪策略：分别基于独立系统和次模函数两个概念介绍了应用贪婪策略设计近似算法的两个一般方法，并介绍了其在最小权集合覆盖等问题中的应用；对非次模函数的优化问题，以最小连通控制集为例介绍如何用贪婪算法求解。（3）限制：介绍限制的概念，该方法通过给优化问题添加约束缩小可行区域。引入Steiner树和生成树、k-Steiner树的概念，并将该方法运用到iterated k-stein tree近似算法分析中。（4）划分：划分可视为限制的特殊情形。针对划分问题主要讲解了移位、双层划分。（5）断切：演示了如何将一个复杂的问题分解为若干个计算复杂度为多项式时间的子问题，以最短矩形划分问题为例进行了详细介绍。（6）松弛：针对不同的优化问题，介绍如何运用松弛技巧，主要讲解了哈密顿圈、单位圆盘图上连通控制集等相关问题，并且给出传感器网络中的实际应用。
堵丁柱教授在近一周的授课时间里，让同学们了解了算法设计的理论与应用方面的最新科研动态和发展，使同学们开阔了眼界。课程结束后，同学们报以热烈掌声，均表示受益匪浅。
堵丁柱教授是世界著名数学家，攻克了斯坦纳比难题。堵丁柱教授1982年硕士毕业于中科院应用数学研究所，1985年获加利福尼亚大学圣巴巴拉分校理论计算机方向数学博士。他先后在美国伯克利大学、麻省理工大学, 普林斯顿大学数学研究所工作。1991年和1995年成为 Minnesota大学计算机系的副教授和教授，并于1987-2002年任中科院应用数学研究所研究员，1998到1999年间任职香港城市大学计算机科学系客座研究员。现任美国自然科学基金委计算机理论的项目主管，美国德克萨斯大学计算机系教授。长期从事组合优化、计算机网络和计算理论、算法与复杂性研究。目前已经发表论文160多篇，编著出版了40本学术著作。他曾获得以美国数学会主席Graham命名的Graham奖、美国国际运筹与管理科学联合会(INFORMS)颁发的CSTS奖，也曾先后获首届中国青年科学家奖、中科院青年科学家奖、中国国家自然科学二等奖、三等奖、中国科学院自然科学一等奖等奖项，担任国际《组合优化》杂志主编以及10多种国际专业杂志编委，是国际组合优化与复杂性研究的著名学者和带头人之一。他于1982年从中国科学院应用数学研究所取得硕士学位后赴美留学，1985年获美国加州大学数学专业博士学位，先后在加州大学、麻省理工学院、普林斯顿大学、明尼苏达大学等多所知名高校任职。
作者:王蕊
