Algorithm and Information Colloquium (AIC)

题目：Weak Kernels

报告人：Binhai Zhu（朱滨海）

时间：2010年3月3日（星期三）下午16:30 – 17:30

地点：软件所5号楼三层报告厅

茶歇：16:00 – 16:30（对面休息室）

摘要：

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 by Minimum Unsigned Reversals problem.

报告人简介：

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.