Solution of Bharathi-Kempe-Salek Conjecture on Influence Maximization
发布时间：2017-06-23 浏览次数：0次
报告简介：
The influence maximization is an important problem in study of social networks. In 2007, Bharathi, Kempe and Salek conjectured that the influence maximization problem is NP-hard for arborescence directed into a root. Recently, this conjecture is proved for the IC model and disproved for the LT model. This is the first result to tell the difference on computational complexity between two important diffusion models, the IC model and the LT model in social networks
报告人简介：
堵丁柱，男，1982年获中国科学院硕士学位，1985年获美国加利福利亚大学圣巴巴拉分校博士学位。1985年～1986年在美国加州伯克利数学科学研究院做博士后，1986～1987年在美国麻省理工大学数学系做助理教授，1987年任中国科学院应用数学所研究员。1990-1991访问 普林斯顿大学计算机科学系。1991-2005年成为明尼苏达大学计算机系的副教授和教授。并于2002-2005任美国国家基金委计算机理论项目主管，2005-2009任西安交通大学理学院院长。现任德克萨斯大学达拉斯分校（UTD）计算机系教授。研究方向包括组合优化，计算机网络和计算理论。已经发表论文200多篇，出版了10本书。《组合优化杂志》和《计算社交网络》的主编，超过15个杂志的编委。1998年获得美国INFORMS的CSTS奖，1993年获得中国自然科学二等奖，1992年获得中国科学院自然科学一等奖。
The influence maximization is an important problem in study of social networks. In 2007, Bharathi, Kempe and Salek conjectured that the influence maximization problem is NP-hard for arborescence directed into a root. Recently, this conjecture is proved for the IC model and disproved for the LT model. This is the first result to tell the difference on computational complexity between two important diffusion models, the IC model and the LT model in social networks
报告人简介：
堵丁柱，男，1982年获中国科学院硕士学位，1985年获美国加利福利亚大学圣巴巴拉分校博士学位。1985年～1986年在美国加州伯克利数学科学研究院做博士后，1986～1987年在美国麻省理工大学数学系做助理教授，1987年任中国科学院应用数学所研究员。1990-1991访问 普林斯顿大学计算机科学系。1991-2005年成为明尼苏达大学计算机系的副教授和教授。并于2002-2005任美国国家基金委计算机理论项目主管，2005-2009任西安交通大学理学院院长。现任德克萨斯大学达拉斯分校（UTD）计算机系教授。研究方向包括组合优化，计算机网络和计算理论。已经发表论文200多篇，出版了10本书。《组合优化杂志》和《计算社交网络》的主编，超过15个杂志的编委。1998年获得美国INFORMS的CSTS奖，1993年获得中国自然科学二等奖，1992年获得中国科学院自然科学一等奖。
