Set Cover and Group Set Cover

活动时间： 10月11日15时30分       

地            点  ： 公教楼E座407教室

讲座内容：

Thereare three optimization problems about set covers, the maximum coverage problem,the minimum set cover problem, and the min-max set cover problem.   For all of them, the greed algorithm   has the best possible performance ratio amongall polynomial-time approximation. However, this is not true for group set cover. In this talk, acomparison is studied between set cover and group set cover. This comparisonwill explore some interesting open problems for our future research.

主讲人介绍：

堵丁柱，男，1982年获中国科学院硕士学位，1985年获美国加利福利亚大学圣巴巴拉分校博士学位。1985年～1986年在美国加州伯克利数学科学研究院做博士后，1986～1987年在美国麻省理工大学数学系做助理教授，1987年任中国科学院应用数学所研究员。1990-1991访问普林斯顿大学计算机科学系。1991年和1995年成为明尼苏达大学计算机系的副教授和教授。并于2002-2005任美国国家基金委计算机理论项目主管，2005-2009任西安交通大学理学院院长。现任德克萨斯大学达拉斯分校（UTD）计算机系教授。研究方向包括组合优化，计算机网络和计算复杂性理论。已经发表论文200多篇，出版了10本书。《组合优化》、《离散数学、算法与应用》和《计算社交网络》的主编，超过15个杂志的编委。1998年获得美国INFORMS的CSTS奖，1993年获得中国自然科学二等奖，1992年获得中国科学院自然科学一等奖。

发布时间：2019-10-10 15:36:18