《網路鏈路選擇問題的近似算法》是依託山東大學，由張鵬擔任項目負責人的面上項目。
基本介紹
- 中文名：網路鏈路選擇問題的近似算法
- 項目類別：面上項目
- 項目負責人：張鵬
- 依託單位：山東大學
中文摘要,結題摘要,
中文摘要
本項目針對NP困難網路鏈路選擇問題的近似算法和不可近似性這一專題開展研究。網路鏈路選擇問題是處理網路連通性的一類網路設計問題，來源於人們對計算機網路和電信網路的底層通信網路的研究。鏈路選擇問題是網路設計問題中的核心問題之一。近似算法是處理NP困難問題的一種本質的方法，關於鏈路選擇問題近似理論的研究是近年來近似算法領域中一個顯著的研究熱點。本項目致力於對鏈路選擇問題中的若干重要NP 困難問題設計快速有效的近似算法，以及探索它們的可近似性下界，這些問題包括Rent-or-Buy和Buy-at-Bulk等典型的鏈路選擇問題。項目組將深度剖析問題及其解的結構和性質，考察問題之間的相互聯繫，從正負兩個方面對鏈路選擇問題的近似求解進行全面的分析與探索。項目的研究將進一步豐富網路鏈路選擇問題的近似理論，並在實際套用領域中產生廣泛的影響。
結題摘要
本項目針對NP困難網路鏈路選擇問題和割問題的近似算法和不可近似性這一專題開展研究。網路鏈路選擇問題關注如何在網路中選取最小費用的邊子集將若干給定終端連線起來，割問題關注如何在網路上去掉最小費用的邊子集將給定的若干終端斷開。因此，網路鏈路選擇問題和割問題是目標對偶的兩類網路設計問題。近似算法是處理NP困難問題的一種本質的方法，關於鏈路選擇問題和割問題近似理論的研究是近年來近似算法領域中一個顯著的研究熱點。本項目致力於對所研究問題設計快速有效的近似算法，以及證明它們的計算複雜性和不可近似性。 項目所取得的主要研究結果包括：（1）對一類部分最佳化問題給出了線性規劃取整加貪心的近似算法設計方法，套用該方法，對樹上推廣的k-多重割問題、k-森林問題等給出了首個近似算法。該結果是近似算法設計方法上的創新，是項目組取得的最為顯著的成果。（2）套用線性規劃取整加貪心的近似算法設計方法，對選擇Buy-at-Bulk網路設計問題給出了全新的近似算法，近似比為O(q^{1/2})。這是自從Awerbuch和Azar在1997年使用樹分解的方法近似選擇Buy-at-Bulk問題以來，近15年的時間裡出現的該問題的首個不同於樹分解方法的非平凡近似算法。（3）通過對一系列割問題的深入研究，得到了最小k-傳導率問題和k-最稀疏割問題的首個近似算法結果，對Leskovec等人在社會網路社區識別中所採取的實驗方法給出了首個理論解釋。（4）使用線性規劃技術，對標籤割問題給出了改進的O((m / OPT)^{1/2})-近似算法和新的O(n^{2/3} / OPT^{1/3})-近似算法，在此OPT為問題的最優解值。並且，證明了算法所使用的線性規劃的整性間隙至少是Omega((m / OPT)^{1/2-epsilon})，從而表明使用給定的線性規劃，近似比O((m / OPT)^{1/2})是理論上所能達到的最好的結果。 項目組共發表SCI索引論文6篇，EI索引論文7篇，以及4篇已線上出版或接受的SCI待檢索論文。這些論文發表在Discrete Applied Mathematics、Journal of Combinatorial Optimization等國際期刊和ISAAC、LATIN等國際會議上。項目的研究進一步豐富了網路設計問題的近似理論，並在實際套用產生潛在的影響。
