蒙大拿州立大學朱濱海教授學術報告20180309

報告題目：參數近似算法簡介

報告時間：2018年3月9日下午14:00

報告地點：旭日樓306教室

主講人：朱濱海教授

主講人簡介：

朱濱海，1994年在加拿大麥吉爾(McGill)大學獲計算機科學博士學位，1994-1996年在美國新墨西哥州Los Alamos國家實驗室完成博士後。自1996年起他分别在香港城市大學及美國蒙大拿州立大學任教。朱濱海教授的研究方向為算法分析與設計(及相關應用)，計算生物，計算幾何等，在相關國際刊物及國際會議上已發表180餘篇學術論文。他的研究4次得到美國NSF支持，2009年及2016年兩次獲中國國家自然科學基金海外與港澳合作研究基金(原海外傑青)支持。

報告簡介：

FPT算法(參數算法)是處理NP-完全優化問題的傳統方法之一。但同時我們已知有些問題(如最大獨立集)是不存在參數算法的，除非FPT=W[1]。在這種情況下，參數近似算法就可能是人們很自然的選擇(雖然該方向的進展相對緩慢)。在這個報告中，我們将對參數算法，W[1]，參數近似算法等用實例作簡單的介紹。最後，列舉該方向的幾個開放問題。