講座題目：Approximating the minimum independent dominating set - Smoothed analysis 2013-06-09

報(bào)告人: 林國(guó)輝教授 加拿大Alberta大學(xué)

時(shí)  間: 2013年6月13日（星期四）上午10：00～11：30

地  點(diǎn): bwin必贏唯一官網(wǎng)313教室

講座內(nèi)容：

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.

林國(guó)輝教授簡(jiǎn)介：

1998年于中科院應(yīng)用數(shù)學(xué)所獲得博士學(xué)位，1998-2001年先后在佛蒙特大學(xué)、加拿大滑鐵盧大學(xué)和麥克馬斯特大學(xué)從事博士后研究，現(xiàn)任加拿大阿爾伯特大學(xué)計(jì)算科學(xué)系教授。林國(guó)輝教授主要研究興趣包括優(yōu)化算法設(shè)計(jì)與分析，機(jī)器學(xué)習(xí)，數(shù)據(jù)庫(kù)和數(shù)據(jù)發(fā)掘和生物信息學(xué)和計(jì)算生物學(xué)。