讲座题目：Approximating the minimum independent dominating set - Smoothed analysis 2013-06-09

报告人: 林国辉教授 加拿大Alberta大学

时  间: 2013年6月13日（星期四）上午10：00～11：30

地  点: 西安交通大学管理学院313教室

讲座内容：

We investigate the minimum independent dominating set in perturbed graphs, obtained by negating the existence of edges independently with a probability. We prove the asymptotic value of the size of the minimum independent dominating set and present a simple greedy algorithm for this problem and with polynomial expected running time.

林国辉教授简介：

1998年于中科院应用数学所获得博士学位，1998-2001年先后在佛蒙特大学、加拿大滑铁卢大学和麦克马斯特大学从事博士后研究，现任加拿大阿尔伯特大学计算科学系教授。林国辉教授主要研究兴趣包括优化算法设计与分析，机器学习，数据库和数据发掘和生物信息学和计算生物学。