报告时间：2018年12月13日上午10：00
报告地点：电教楼211（经管学院）
Title: Algorithms to Handle NP-hard Problems
题目: 解决NP-难问题的算法
Abstract: Many important combinatorial problems are NP-hard, but we still need to solve them. Approximation algorithms and FPT algorithms are two solutions which solve NP-hard problems with some performance guarantee. In this talk I will introduce these two methods with simple examples and I will also review some of my recent results along the line (a 2k-kernel for Vertex Cover and a 2-approximation for Contig-based Scaffold Filling). This talk is self-contained and no prior knowledge on algorithms is needed.
摘要：虽然许多重要的组合优化问题是NP-难问题，但是在现实中我们仍然需要解决方案。近似算法和FPT算法是具有性能保障的两种应对NP-难问题的解决方案。本次讲座将就一些简单的实例来介绍这两种方法，并总结本人最新的研究成果(a 2k-kernel for Vertex Cover and a 2-approximation for Contig-based Scaffold Filling)。本次讲座可以不需要算法的基础，欢迎各位老师和同学参加研讨。
主讲人简介：朱滨海，1994年在加拿大麦吉尔(McGill)大学获计算机科学博士学位，1994-1996年在美国新墨西哥州Los Alamos国家实验室完成博士后。自1996年起他分别在香港城市大学及美国蒙大拿州立大学任教。朱滨海教授的研究方向为算法分析与设计(及相关应用)，计算生物，计算几何等，在相关国际刊物及国际会议上已发表180余篇学术论文。他的研究4次得到美国NSF支持，2009年及2016年两次获中国国家自然科学基金海外与港澳合作研究基金(原****)支持。