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