应计算机系主任郑庆华教授的邀请,美国 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.

电信学院计算机系