题目：偏亚线性时间关于最大覆盖问题近似
报告人：付斌 教授
地点：学院101会议室
时间：2017年1月9日 下午2：30
学术报告简介：
付斌博士在此报中将介绍他最近发展的关于偏亚线性时间概念并用于改进古典的最大覆盖问题的算法。最大覆盖问题有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。他主要的研究领域为计算机算法及其计算复杂性。