美国德克萨斯州立大学Rio Grande Valley分校付斌教授到我院学术交流

2017年1月9日下午,美国德克萨斯州立大学Rio Grande Valley分校计算机科学系付斌教授应邀到计算机学院进行学术交流,作了题为《偏亚线性时

2017年1月9日下午,美国德克萨斯州立大学Rio Grande Valley分校计算机科学系付斌教授应邀到计算机学院进行学术交流,作了题为《偏亚线性时间关于最大覆盖问题近似》的学术报告。报告会由学院院长汤庸教授主持,计算机学院老师和研究生参与了本次报告会。

1.jpg

付斌以计算机经典问题P问题和NP问题为引入,介绍了NP困难性算法中的近似算法。在报告中,付斌着重介绍了其最近发展的关于偏亚线性时间概念并用于改进古典的最大覆盖问题的算法,提出以下自然计算摸型:毎个集合在单位时间允许产生随机元素,允许询向某个元素是否在此集合中及其此集合大小,导岀算法时间为poly(m),并且保持古典的1-1/e的近似精度。

2.jpg

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