2935
9
0
2017-01-09 15:26:49
2017-01-10
2017年1月9日，美國德州大學(xué)大河谷分校付斌教授和中山大學(xué)數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院劉詠梅教授訪問實(shí)驗(yàn)室。付斌教授在學(xué)院做了題為“偏亞線性時(shí)間關(guān)于最大覆蓋問題近似”的學(xué)術(shù)報(bào)告。
學(xué)術(shù)報(bào)告簡介：
付斌博士在此報(bào)中將介紹他最近發(fā)展的關(guān)于偏亞線性時(shí)間概念并用于改進(jìn)古典的最大覆蓋問題的算法。最大覆蓋問題有A1, ..., Am 共m個(gè)輸入有限集合和參數(shù)k, 要求找到其中的k個(gè)集并且并集最大。這是一個(gè)具有廣泛應(yīng)用的古典問題，他提出以下自然計(jì)算摸型：毎個(gè)集合在單位時(shí)間允許產(chǎn)生隨機(jī)元素，允許詢向某個(gè)元素是否在此集合中，及其此集合大小。他導(dǎo)岀算法時(shí)間為poly(m), 并且保持古典的1-1/e的近似精度。也就是說計(jì)算時(shí)間獨(dú)立于最大集合的大小n。
報(bào)告人簡介：
付斌為美國德克薩斯州立大學(xué)Rio Grande Valley分校計(jì)算機(jī)科學(xué)系教授。他于1985年和1988年分別獲得武漢大學(xué)計(jì)算機(jī)科學(xué)學(xué)士和碩士學(xué)位，1998年獲美國耶魯大學(xué)計(jì)算機(jī)科學(xué)博士學(xué)位。付斌在1988至1993任教于北京計(jì)算機(jī)學(xué)院，1997至1998在Lehigh大學(xué)從事博士后研究，1998到1992在美國硅谷工業(yè)界從事圖象處理和網(wǎng)絡(luò)算法及其軟硬件的開發(fā)和研究，2003至2006任教于美國新奧爾良大學(xué)計(jì)算機(jī)科學(xué)系助理教授，2006轉(zhuǎn)入徳克薩斯州立大學(xué)Pan American分校（現(xiàn)Rio Grande Valley分校），2009年獲得副教授，2012獲得正教授，付斌博士于2009年獲得美國NSF Early Career Award。他主要的研究領(lǐng)域?yàn)橛?jì)算機(jī)算法及其計(jì)算復(fù)雜性。
