講座題目：Approximating the minimum independent dominating set - Smoothed analysis 2013-06-09 報告人: 林國輝教授 加拿大Alberta大學時 間: 2013年6月13日（星期四）上午10：00～11：30地 點: bwin必贏唯一官網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年先后在佛蒙特大學、加拿大滑鐵盧大學和麥克馬斯特大學從事博士后研究，現任加拿大阿爾伯特大學計算科學系教授。林國輝教授主要研究興趣包括優(yōu)化算法設計與分析，機器學習，數據庫和數據發(fā)掘和生物信息學和計算生物學。