7月13日至7月17日，应中国科学院大学数学科学学院的邀请，美国德克萨斯州大学堵丁柱教授在雁栖湖校区教学楼209教室开设了深受广大研究生欢迎的夏季学期课程《近似算法的分析与设计》。
堵丁柱教授的《近似算法的分析与设计》课程主要由以下5部分组成：（1）算法的相关知识：介绍了社会网络的基础知识，引出本课程内容的具体应用。P、NP的概念、近似比的介绍，以背包问题为例讲解了如何估计一些经典的NP完备问题的近似比。（2）贪婪策略：分别基于独立系统和次模函数两个概念介绍了应用贪婪策略设计近似算法的两个一般方法，并介绍了其在最小权集合覆盖问题等中的应用。对非次模函数的优化问题，以最小连通控制集为例介绍如何用贪婪算法求解。（3）限制：介绍限制、Steiner树和生成树、k-Steiner树的概念，并将该方法运用到iterated k-stein tree近似算法分析中。（4）松弛：针对不同的优化问题，介绍如何运用松弛技巧。主要讲解了哈密顿圈、单位圆盘图上连通控制集等相关问题，并且给出传感器网络中的实际应用。（5）近似难度: 介绍L-规约, APX-完全性概念，讨论如何证明一些NP-难解问题的优化问题的不可近似性。
为期一周的课程结束后，同学们报以热烈掌声。堵丁柱教授深入浅出的讲解让同学们了解了在算法设计的理论与应用方面的最新科研动态和发展，使同学们受益匪浅。
堵丁柱教授是国际计算机理论科学和组合优化领域的顶级专家、国际著名应用数学与运筹学专家，美国德克萨斯大学达拉斯分校计算机科学系教授，中国科学院大学兼职教授。他也是中国科学院数学与系统科学研究院应用数学研究所客座教授、中国人民大学客座教授，香港城市大学访问教授。因解决著名的Steiner 比猜想，Derman-Leiberman-Ross 猜想和Rosen 投影梯度法的全局收敛性的工作而闻名，曾获得以美国数学会主席Graham命名的Graham奖、美国国际运筹与管理科学联合会(INFORMS)颁发的CSTS奖，也曾先后获首届中国青年科学家奖、中科院青年科学家奖、中国国家自然科学二等奖、三等奖、中国科学院自然科学一等奖等奖项。长期从事组合优化、计算机网络和计算理论、算法与复杂性研究，目前已经发表高水平研究论文180多篇，编著出版了40余部学术著作，担任国际《组合优化》杂志主编以及10多种国际专业杂志编委，是国际组合优化与复杂性研究的著名学者和带头人之一。
作者:王蕊
