首页
学院新闻
学院公告
学术信息
就业信息

学术报告“偏亚线性时间关于最大覆盖问题近似”

来源: 点击: 时间: 2016年12月28日 10:24

报告题目:偏亚线性时间关于最大覆盖问题近似

报告时间:2017年1月3日上午10:00

报告地点:升华后楼215

报告简介:

付斌博士在此报中将介绍他最近发展的关于偏亚线性时间概念并用于改进古典的最大覆盖问题的算法。最大覆盖问题有A1, ..., Am 共m个输入有限集合和参数k, 要求找到其中的k个集并且并集最大。这是一个具有广泛应用的古典问题,他提出以下自然计算摸型:毎个集合在单位时间允许产生随机元素,允许询向某个元素是否在此集合中,及其此集合大小。他导岀算法时间为poly(m), 并且保持古典的1-1/e的近似精度。也就是说计算时间独立于最大集合的大小n。

付斌愽士简介:

付斌为美国德克萨斯州立大学Rio Grande Valley分校计算机科学系教授。他于1985年和1988年分别获得武汉大学计算机科学学士和硕士学位,1998年获美国耶鲁大学计算机科学博士学位。付斌在1988至1993任教于北京计算机学院,1997至1998在Lehigh大学从事博士后研究,1998到1992在美国硅谷工业界从事图象处理和网络算法及其软硬件的开发和研究,2003至2006任教于美国新奥尔良大学计算机科学系助理教授,2006转入徳克萨斯州立大学Pan American分校,其变今天Rio Grande Valley分校,2009年获得副教授,2012获得正教授,付斌博士于2009年获得美国NSF Early Career Award。他主要的研究领域为计算机算法及其计算复杂性。


返回首页

上一条:日本大阪府立大学Hisao Ishibuchi教授报告会

下一条:美国宾夕法尼亚大学龙琦教授学术报告及交流会