学部新闻

当前位置: 首页 > 学部新闻 > 头条新闻 > 正文

头条新闻

学 术 报 告

日期:2010-05-14    点击数:     来源:

应计算机系主任郑庆华教授的邀请,美国 Montana State University 计算机科学系朱滨海教授来我系进行学术交流,欢迎广大教师、研究生参加!

题目:Weak Kernels and Its Applications(亚核心及其应用)

时间:2010年5月14日(星期五)下午3:00-4:00

地点:电信学院第一会议室344

Abstract:

Fixed-parameter algorithm is a well-known method to handle NP-complete problems. Kernelization is a standard concept/method in fixed-parameter computation, which can be thought of as data reduction. In this talk, I will introduce `weak kernels' for fixed-parameter computation, which is roughly reducing solution search space for hard optimization problems. It can be shown that if a problem has a (traditional) kernel then it also has a weak kernel. The converse is not always true for problems beyond NP.For a problem in NP, it can be shown that if it has a weak kernel then it admits an FPT algorithm (hence a kernel). I will sketch a few applications of weak kernels, for which a (traditional) kernelization seems hard to apply. Among them, I will present the first FPT algorithm for the famous Sorting byMinimum Unsigned Reversals problem.

Short CV

Dr. Binhai Zhu obtained his PhD from McGill University, Canada in 1994.He did his post-doc at Los Alamos National Laboratory, NM, USA between 1994 and 1996. Since 1996 he has taught in Hong Kong, Canada and USA. He is currently a professor at the Computer Science Department, Montana State University, USA. He has published over 100 papers in international journals and conference proceedings. He was the program committee co-chair for COCOON'2003, AAIM'2005, and COCOA'2007. His current research interests are mainly in computational biology, FPT algorithms and computational geometry. More information can be found on his web page at http://www.cs.montana.edu/bhz.

电信学院计算机系

2010年5月13日

关闭

版权所有:电子与信息学部 技术支持与维护:西安交通大学网络信息中心 联系人:李老师 029-82668661
地址:陕西省西安市咸宁西路28号 邮编:710049