卓越研究

翁振剛同學獲得2009年度工程學院 “傑出畢業論文獎”

祝賀翁振剛同學(劉立志教授所指導的碩士研究生)榮獲工程學院2009年度“傑出畢業論文獎”。

 

翁同學的畢業論文“Edge Splitting-off and Network Design Problems”的研究動機源自於Degree Bounded Network的設計問題。這個題目了涉及了組合優化方面的一些重要問題,並且它在許多領域有著實際應用。然而,該演算法的複雜度無法用多項式逼近,因為,即使對於找到一棵擴展樹這樣的簡單情況,該問題都是一個NP-Hard問題。

 

這篇論文顯示,在度量成本下,對於Degree Bounded Network設計問題而言,有複雜度為常數因數多項式逼近的演算法。這些演算法中的主要技術工具是一個名為“Edge Splitting-Off”的組合操作。除了網路設計以外,這項技術還廣泛應用於一些其他的邊連接度問題上。通過拓展和改善一些Edge Splitting-Off的結果,我提出了Efficient Edge Splitting-Off演算法,這一演算法通過參數改善了最為人熟知的結果的時間複雜度。這些演算法中概念上十分簡單,並且可以被拓展到其他不同的設定上。另外,Mr. Yung還把Edge Splitting-Off演算法拓展到合併一些額外約束,並應用這些結果來為一些Constrained Connectivity Augmentation問題提供提供的近似演算法。