由中国科学院研究生院数学科学学院邀请的堵丁柱教授于6月28日下午，在中关村园区教学楼S104开设了深受广大研究生欢迎的《近似算法的设计与分析》夏季学期课程。
堵教授长期从事组合优化、计算机网络和计算理论、算法与复杂性的研究。目前已经发表论文160多篇，出版书籍40本。他是组合优化杂志和系列书籍《网络理论和应用》的主编， 还是超过15个杂志的编委。关于吉尔伯特-波拉克猜想的证明被西方媒体广泛报道，并被大英百科全书选为1991年数学科学六大杰出成就之首。他曾获国家自然科学二等奖、中国青年科学家奖、美国格雷汉姆奖和CSTS奖，担任国际《组合优化》杂志主编以及10多种国际专业杂志编委，是国际组合优化与复杂性研究的著名学者和带头人之一。他于1982年从中国科学院应用数学研究所取得硕士学位后赴美留学，1985年获美国加州大学数学专业博士学位，曾在伯克利数学研究所从事博士后研究，先后在加州大学、麻省理工学院、普林斯顿大学、明尼苏达大学等多所知名高校任职。
堵教授的《近似算法的设计与分析》课程设置主要由以下5部分组成：（1）算法的相关知识：P、NP概念的引入，讲解了如何估计一些经典的NP完备问题的近似比。（2）带有非次模势函数的近似贪婪算法分析：分析了目前几乎所有的贪婪算法的理论分析中所隐含的次模势函数，唯一的例外是Steiner树中的iterated k-stein tree问题。进一步讲解了此时该如何采用新的方法去分析该问题，得到贪婪算法的近似比。内容还同时涉及了了在无线网络的功率分配等方面。（3）矩阵划分问题：堵老师详细演示了如何将一个复杂的问题分解为若干个计算复杂度为多项式时间的子问题，并且用求解“将含有矩阵形状洞的直线多边形划分为若干矩阵，使得添加的边长度最小”示例。（4）网络优化问题中的近似算法：列举了网络中的一些问题目前的近似算法，让大家了解了目前近似算法的应用，开阔了眼界。（5）线性规划和非线性规划，并给出了现有算法的近似比的证明过程。
当堵丁柱教授结束课程时，同学们报以了热烈的掌声。堵教授的课程让同学们了解了在算法设计的理论与应用方面的最新科研动态和发展，同学们都表示自己从短短几周的课程中受益匪浅。
