肖鳴宇 電子科技大學計算機科學與工程學院教授、博士生導師,協同自主計算實驗室。多個基本NP難問題的最佳參數和精確算法的保持者,在圖的多分割問題上解決了多個公開難題,在參數算法上是國內最為活躍的科研工作者之一。
"在香港中文大學師從圖靈獎獲得者姚期智先生,從事理論計算機方向博士學習三年獲得博士學位。清華大學、京都大學、巴黎第九大學等高校訪問學者。科研方向包括:算法與計算複雜度分析,圖論及圖算法,智慧型算法,最最佳化,參數算法等。
和日本、加拿大、美國、法國、以色列、香港等地許多計算機專家建立了學術合作關係。目前是多個基本NP難問題的最佳參數和精確算法的保持者,在精確算法和參數算法上是國內最為活躍的科研工作者之一。主持國家自然科學基金4項。近五年第一作者發表高水平學術論文50餘篇。
基本介紹
- 中文名:肖鳴宇
- 職業:教授、博導
- 性別:男
- 學歷:博士
- 工作:電子科技大學協同自主計算實驗室
簡介,教育背景,科研情況,主持項目,招生方向,人物介紹,發現天賦:算法奇才讓人眼前一亮,得遇名師:在算法領域落地生根,潛心研究:在基礎與前沿領域馳騁,發表論文,教學情況,
簡介
姓名:肖鳴宇 | 性別:男 | 學校:電子科技大學 |
系別:軟體系 | 職稱:教授、博士生導師 | 畢業院校:中南大學 |
學歷:博士 | 實驗室:協同自主計算實驗室 | 電話: |
研究方向:算法設計與分析,計算複雜度分析,近似算法,參數算法,圖論及圖算法,計算機輔助幾何設計等 |
教育背景
2008年,博士,計算機,香港中文大學(The Chinese University of Hong Kong)
2009年6月,2010年7月,訪問學者,京都大學(Kyoto University)
2011年9-11月,訪問學者,巴黎九大(University Paris Dauphine)
科研情況
肖鳴宇在香港中文大學師從圖靈獎獲得者姚期智先生,從事理論計算機方向學習三年獲得博士學位。和日本、加拿大、美國、法國、以色列、香港等地許多計算機專家建立了學術合作關係。目前是多個基本NP難問題的最佳參數和精確算法的保持者,在圖多分割問題上解決了多個公開難題,在參數算法上是國內最為活躍的科研工作者之一。主持國家自然科學基金4項。近四年第一作者發表高水平學術論文近40篇,其中8篇屬於CCF認定的B類及以上刊物,7篇屬於CCF認定C類刊物。
目前主要從事參數算法和精確算法方向研究。在《Algorithmica》等國際頂級算法雜誌和會議上第一作者發表論文20餘篇(具體列表參看DBLP或谷歌主頁)。主持國家自然科學基金青年項目《圖上若干基本NP難問題的算法研究》、國際交流與合作項目《獨立集、點覆蓋及其相關問題的參數算法和精確算法研究》等三項國家級項目。
肖鳴宇老師一直從事算法方向研究工作,他的研究成果之一:為獨立集問題設計了當前最快的精確算法,是近30年來第一次真正打破Robson於1986年給出的運行時間上界,並在亞太地區算法與計算領域最好的會議ISAAC 2013上獲最佳論文提名;2013年獲國家自然科學基金面上資助,發表第一作者論文10篇(其中SCI 5篇,CCF B類4篇),獲校學術新人獎,是計算機學科第一位獲得該資助的青年老師。肖鳴宇老師承擔的課程被評定優秀,同時他還擔任了數理基科班和學院珠峰計畫導師,指導本科生髮表一級學報論文1篇。
主持項目
1.基於“測量治之”方法的算法設計研究,國家自然科學基金,主持
2. 圖上若干基本NP難問題的算法研究,國家自然科學基金,主持
3. 獨立集、點覆蓋及其相關問題的精確算法和參數算法研究,國家自然科學基金,主持
4. Online Optimization for Dynamic Power Management, 國家自然科學基金,中方主持
5. 參數算法理論及其套用研究,中央高校基金,主持
6. 圖分割問題的參數算法研究,電子科技大學校青年科學基金,主持
招生方向
博士招生專業 | 碩士招生專業 |
081202計算機軟體與理論 | 081202計算機軟體與理論 |
04方向:計算生物學 06方向:計算智慧型 08方向:複雜網路分析 | 02方向:資料庫與數據挖掘 05方向:計算理論與技術 10方向:計算生物學 |
人物介紹
肖鳴宇教授又攻下了一個基礎性計算難題——改進獨立集問題的精確算法,打破了國際著名算法理論大師羅賓遜在1986年創下的紀錄。這個難題已經讓算法理論界頭疼近30年,肖鳴宇從博士畢業到紮根電子科大,一直堅持不懈地潛心研究了整整五年。![肖鳴宇 肖鳴宇](/img/9/b6e/nBnauI2M2YmY3EGM1kDZxYDMkZTMzYTZ0MmNjlTO4IGNykTZwMjZxgzM5IzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
![肖鳴宇 肖鳴宇](/img/9/b6e/nBnauI2M2YmY3EGM1kDZxYDMkZTMzYTZ0MmNjlTO4IGNykTZwMjZxgzM5IzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
這是理論計算領域套用十分廣泛且最為基礎的難計算問題之一。近30年來,圍繞這個獨立集問題精確算法的研究論文不下20篇,但都沒有超越羅賓遜的研究——肖鳴宇卻使“羅賓遜”又往前走了一大步。
2013年底,當肖鳴宇應邀參加在香港舉行的第25屆國際算法與計算大會(ISAAC)時,此文作為重要研究成果,入選大會“最佳論文”候選論文,並受到業內學者的高度關注。
肖鳴宇沒有拿過多少“大項目”,而是一門心思深入到“收效周期很長”的基礎計算理論研究,並樂此不疲。雖然這項研究的更大價值或許要在5年之後才能充分顯現,但他認為,作為基礎與前沿理論的研究者,這已足以讓他感到快慰了。
發現天賦:算法奇才讓人眼前一亮
肖鳴宇本科時就讀於中南大學數學系,做的最多且最有樂趣的事情,就是參加數學建模競賽。當時,他在同學們眼裡是當之無愧的數學建模高手,曾在美國數學建模競賽中連續兩次斬獲一等獎。
從數學到計算機,只有一步之遙,數學建模或算法研究就是這樣一種數學與計算機交叉融合的典型。很多學科都會遇到數學建模或算法研究,肖鳴宇的所有努力可以劃分為兩個步驟:第一是對問題進行最佳化建模,第二是對最佳化模型進行算法設計來求解。
他對算法很感興趣,但一直沒有系統學習過,而是隨著“求解”的需要,東一榔頭、西一棒槌,現學現用。2002年和2005年他在中南大學分別獲得數學學士和碩士學位,並獲得湖南省優秀畢業論文和湖南省優秀畢業生稱號——但這些與算法沒有多少關聯,直到上博士當助教時,為了給香港中文大學的本科生講課,他才系統接觸了算法課程。
以此為標誌,他徹底從數學轉入算法研究,再也沒有變更過方向。算法是計算機領域內十分基礎的理論,他說,“計算機是死的,你得用算法告訴它做什麼、怎么做,因此,計算機的智慧就取決於你的思想!”
其實,肖鳴宇並非從一開始就選擇算法為畢生事業,當他在數學的海洋遨遊時,甚至從未想到自己以後會和算法結下如此深厚的情誼。促使他發生轉變的是一個“中南傳奇”:二十年前,有一位數學天才轉行做了算法研究,並成為算法領域的巨擘。
這個人就是美籍華人學者、當時中南大學的“長江學者”陳建二教授。陳建二多年來主要從事計算機理論及套用技術的研究,在計算複雜性理論、圖理論與算法、計算最佳化理論、網路理論等領域內進行了深入系統的研究,取得了一批具有世界領先水平的理論成果。
一位數學奇才何以轉入算法領域?帶著這個困惑和對自己未來方向的思索,肖鳴宇鼓起勇氣求教陳建二教授。他聽完肖鳴宇的疑問之後,並沒有直接回答,而是隨口出了幾個算法難題;肖鳴宇略加思索,即給出了自己的答案。這讓陳建二頓時對眼前的這個小伙子刮目相看,他認為,肖鳴宇的解決思路與算法領域近十年來的前沿思想十分吻合,甚至有一些思路獨闢蹊徑,有過之而無不及。
於是,陳建二果斷建議肖鳴宇向算法研究轉型,“雖然做數學研究也可以做出傑出的成就,但如果不做算法研究就太可惜了!”在肖鳴宇碩士畢業時,陳建二欣然為他寫了推薦信,薦他到香港中文大學蔡雷震教授麾下學習。不料,蔡雷震憐愛肖鳴宇之才,立即鼎力推薦給了學界泰斗——姚期智院士。
姚期智是世界著名計算機學家、美國科學院院士、美國科學與藝術學院院士、中國科學院外籍院士,2000年“圖靈獎”得主。2004年9月,他辭去美國普林斯頓大學的終身教職,正式加盟清華大學高等研究中心,成為清華的全職教授,並於2005年成為香港中文大學的博文講座教授。
2005年,肖鳴宇在蔡雷震的推薦下,在香港中文大學見到了他的博士生導師姚期智。3年後,他就獲得了哲學博士學位,成為姚期智在香港中文大學培養出的第一位博士,也是2008年香港中文大學計算機系僅有的兩位三年畢業的博士之一。
得遇名師:在算法領域落地生根
第一次與導師見面時,肖鳴宇並沒有立即引起姚期智的特別注意。與如此大師級的學者面對面交談,讓他感覺很緊張。見面之前他已做了充分準備,“以為會問到很高層次的問題,所以準備時和見面回答時,都努力往哲學方面靠,結果適得其反,給姚老師留下了一種誇誇其談的形象!”姚期智的考察很實在、很直接,只說了一句“你把Ramsey定理給我證明一遍”。這次見面,讓肖鳴宇學到了很多,也對導師的求實和嚴謹精神由衷地敬佩。
半年後,姚期智給了第二次見面的機會。經過半年的調整和摸索,肖鳴宇把自己半年來的思考和想法實實在在地做了匯報,讓姚期智十分滿意,他認為肖鳴宇的進步超乎想像。肖鳴宇也從此獲得了更多的見面機會,並有機會聆聽更多的指導。
經過幾次見面交流,姚期智對肖鳴宇在算法方面的靈感和問題意識非常看好。在第三次見面時,他對肖鳴宇的研究方向進行了充分的評估,建議他在“圖算法”和“NP難問題”領域開疆擴土。當時,姚期智主攻“量子計算”,肖鳴宇也曾考慮這個方向,但姚期智卻認為肖鳴宇在“圖算法”和“NP難問題”方面將會取得更大的成就。
此後,肖鳴宇不負所望,在算法領域非常前沿的“圖多最佳化分割問題”研究中取得巨大進展。當時“圖多最佳化分割問題”研究中有多個懸而未決的“公認難題”,肖鳴宇沉浸其中,高度專注,在一周內破解了其中一個難題。當他把最終研究結果報告給“副導師”蔡雷震後,蔡雷震十分重視,但沒有立即給出答覆,而是報告給姚期智。
事後才知道,兩位導師都在獨立地對該研究進行科學嚴謹的驗證。一個月後,肖鳴宇再次見到姚期智,驚訝地發現辦公桌上有100多頁的手寫演算稿紙,對自己研究中的每個步驟都給予了推導和證明——結論是正確的!
以此為開端,肖鳴宇在博士期間獲得了大豐收,不僅成為國內算法理論方向最為活躍的科研者之一,也是多個基本NP難問題最佳參數算法和精確算法的保持者。姚期智、王魯生等教授曾這樣評價肖鳴宇:“他研究的這些問題都十分重要,其中大部分問題被國際頂尖學者廣泛研究。我們相信,他將在這些領域取得更顯著的進展!”
在參數算法基本問題的“Benchmark列表”中,收錄著肖鳴宇的兩項研究結果,是僅有的兩項來自中國的研究結果。他提出的複雜參數方法簡化並改進了很多基本參數算法,被國際同行評價為“有趣並有前景”。
潛心研究:在基礎與前沿領域馳騁
一個又一個公認難題的解決,讓肖鳴宇在學術界聲名鵲起,姚期智也大力推薦這位得意弟子參加相關的國內外高級別學術會議,讓肖鳴宇大開了眼界,同時也在國際學術界獲得了聲譽。
博士畢業後,日本京都大學每年都邀請肖鳴宇赴日本訪問交流,並且每年都派人來中國學習。肖鳴宇加盟電子科大後,京都大學的學者每年都來清水河畔拜訪他。京都大學為肖鳴宇專門留出寬敞的辦公室,並邀請他“任何時候都可以來京都大學辦公”。
“成名”之後,肖鳴宇本來有更多的機會獲取更多的資源做“套用研究”,但是,他一直不肯邁出這一步。導師姚期智也十分希望肖鳴宇堅持做“理論研究”而非“套用研究”,他曾對肖鳴宇說:“我相信你有能力在套用研究中解決一些重大問題,但如果在基礎理論研究中取得突破,將會對學術界和產業界產生更大、更為深遠的影響。”
因此,從博士畢業到現在,肖鳴宇都把自己定位在基礎計算理論研究。“解決大家都解決不了的難題或不願意投身研究的基礎問題,也是一種成功的學術路徑”,他說,“我就是那種專注地解決難題的人!”
肖鳴宇說到做到,從2008年加盟電子科大,他一直致力於基礎研究,沒有接過任何“橫向項目”。“圖多最佳化分割”理論在計算機、積體電路的生產中具有十分廣泛而重要的套用價值,華為等公司多次邀請肖鳴宇做“橫向項目”,助力解決相關技術難題,但肖鳴宇都決然地拒絕了。2009年,他只做成了一件事情,就是成功申請了一項國家自然科學基金——《圖上若干基本NP難問題的算法研究》。
“從理論研究到產業套用有一定的距離,我的精力有限,沒有更多的時間去解決套用領域的問題,所以只能集中力量深入研究基礎理論!”肖鳴宇說,“我相信,只要基礎理論獲得突破,從理論到套用的實現環節肯定會有其他優秀的人才努力完成!”
然而,純粹沉浸在基礎理論研究,對心態和定力是一種極大的考驗。經濟收入、量化考評、職稱晉升等,既是對基礎理論研究者的壓力,也是對他們的極大誘惑。但是,肖鳴宇對此淡然處之,一直選擇在基礎理論領域堅守!
由於“圖算法”和“NP難問題”等領域曲高和寡,國際上相關的學術期刊影響因子較小,論文引用數量不大。而國內的相關研究因起步較晚,氣氛並未廣泛形成,目前大陸僅有清華、北大、上海交大、中南大學等少數幾所高校致力於此。但是,肖鳴宇並不在乎“熱門”還是“冷門”,而是持之以恆,並希望把我國西南地區的這個學科方向撐起來!
近幾年來,肖鳴宇每年都參加許多次各種計算理論方向的重要國際會議,從最開始的“默默無聞”逐步發展為今天的“備受矚目”,肖鳴宇也將“電子科大”推介到了重要的國際學術會議,使其成為國際國內同行最為熟知的內地高校之一。“做大做強計算機基礎與前沿理論,這是我的興趣,也是我的責任!”肖鳴宇說,“做基礎理論研究需要靜心靜氣,在這條路上,我將一如既往、風雨兼程!”
發表論文
Mingyu Xiao:A New Linear Kernel for Undirected Planar Feedback Vertex Set: Smaller and Simpler.AAIM 2014: 288-298
Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Dominating Induced Matching Based on Graph Partition.CoRR abs/1408.6196(2014)
Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Annotated Edge Dominating Set in Graphs with Degree Bounded by 3.IEICE Transactions 96-D(3): 408-418 (2013)
Mingyu Xiao,Hiroshi Nagamochi:Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs.Theor. Comput. Sci. 469: 92-104 (2013)
Mingyu Xiao,Takuro Fukunaga,Hiroshi Nagamochi:FPTASs for trimming weighted trees.Theor. Comput. Sci. 469: 105-118 (2013)
Mingyu Xiao,Hiroshi Nagamochi:Parameterized edge dominating set in graphs with degree bounded by 3.Theor. Comput. Sci. 508: 2-15 (2013)
Mingyu Xiao,Ton Kloks,Sheung-Hung Poon:New parameterized algorithms for the edge dominating set problem.Theor. Comput. Sci. 511: 147-158 (2013)
Mingyu Xiao,Hiroshi Nagamochi:An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs.FAW-AAIM 2013: 72-83
Mingyu Xiao,Hiroshi Nagamochi:An Improved Exact Algorithm for Undirected Feedback Vertex Set.COCOA 2013: 153-164
Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Maximum Independent Set.ISAAC 2013: 328-338
Mingyu Xiao,Hiroshi Nagamochi:An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure.TAMC 2013: 96-107
Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Maximum Independent Set.CoRR abs/1312.6260(2013)
Mingyu Xiao,Hiroshi Nagamochi:An FPT algorithm for edge subset feedback edge set.Inf. Process. Lett. 112(1-2): 5-9 (2012)
Mingyu Xiao,Hiroshi Nagamochi:An Improved Exact Algorithm for TSP in Degree-4 Graphs.COCOON 2012: 74-85
Bruno Escoffier,Jérôme Monnot,Vangelis Th. Paschos,Mingyu Xiao:New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set.IPEC 2012: 25-36
Mingyu Xiao,Jiong Guo:A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments.MFCS 2012: 825-835
Mingyu Xiao,Hiroshi Nagamochi:A Refined Exact Algorithm for Edge Dominating Set.TAMC 2012: 360-372
Mingyu Xiao,Hiroshi Nagamochi:An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure.CoRR abs/1212.6831(2012)
Mingyu Xiao,Leizhen Cai,Andrew Chi-Chih Yao:Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimumk-Way Cut Problem.Algorithmica 59(4): 510-520 (2011)
Mingyu Xiao,Hiroshi Nagamochi:Parameterized Edge Dominating Set in Cubic Graphs - (Extended Abstract).FAW-AAIM 2011: 100-112
Mingyu Xiao,Hiroshi Nagamochi:Further Improvement on Maximum Independent Set in Degree-4 Graphs.COCOA 2011: 163-178
Mingyu Xiao,Ton Kloks,Sheung-Hung Poon:New Parameterized Algorithms for the Edge Dominating Set Problem.MFCS 2011: 604-615
Mingyu Xiao,Ton Kloks,Sheung-Hung Poon:New parameterized algorithms for edge dominating set.CoRR abs/1104.4160(2011)
Mingyu Xiao:Finding minimum 3-way cuts in hypergraphs.Inf. Process. Lett. 110(14-15): 554-558 (2010)
Mingyu Xiao:Simple and Improved Parameterized Algorithms for Multiterminal Cuts.Theory Comput. Syst. 46(4): 723-736 (2010)
Mingyu Xiao:Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs.COCOA (2) 2010: 387-400
Mingyu Xiao:A Note on Vertex Cover in Graphs with Maximum Degree 3.COCOON 2010: 150-159
Mingyu Xiao,Takuro Fukunaga,Hiroshi Nagamochi:FPTAS's for Some Cut Problems in Weighted Trees.FAW 2010: 210-221
Mingyu Xiao:A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs.WALCOM 2010: 281-292
教學情況
肖鳴宇教授除完成本科教學任務外,每年都會招收多名研究生。對於科研工作出色的學生,將推薦到海外交流或深造。其科研分為基礎科研和工程套用兩部分,具體參照如下:
1.基礎科研:建議想從事基礎算法研究的學生報考,特別是有一定數學分析能力或競賽經歷的同學。此方向的學習將大大加強學生的科研基礎。對於有志將來從事科研工作和出國深造的同學,可以考慮學習此方向。科研內容主要包括:算法分析與設計,最佳化算法,圖論及圖算法等。
該方向主要希望培養未來的大學教授和科研者,當然也包括大公司的高級研發人員。學生學習階段以學習和發表學術論文為主,論文達到一定級別則可推薦海外交流。
2. 工程套用:肖鳴宇教授也會招收工程方向的學生,該部分學生主要由實驗室聯合培養,從事雲計算方面的工程學習和鍛鍊。學生將進入雲計算及相關實驗室學習研究,同時將可能獲得其他資深老師的指導。