《精確計算和參數計算的算法新技術》是依託中南大學，由陳建二擔任項目負責人的面上項目。
基本介紹
- 中文名：精確計算和參數計算的算法新技術
- 項目類別：面上項目
- 項目負責人：陳建二
- 依託單位：中南大學
項目摘要,結題摘要,
項目摘要
精確算法和參數算法是近二十年來發展起來的用以求解NP-難問題的方法，它引起了人們廣泛的關注。為了進一步推廣精確算法和參數算法在實際中的套用，開發用來設計更加快速的精確算法和參數算法的新技術就顯得尤為重要。本項目將從新的角度研究精確計算和參數計算的算法新技術，並將這些技術套用到求解許多重要NP-難問題的過程中。本項目研究內容主要包括：（1）從一些具體的經典NP-難問題出發，挖掘出它們的新的量度；（2）基於圖分割和組合對偶，開發出新的核心化技術；（3）結合已有的代數知識，開發新的代數技術，用以設計精確算法和參數算法。.本項目的研究成果將對如何設計高效的精確算法和參數算法起到重要作用，並對求解實際套用中的難解問題有著重大的意義。
結題摘要
在本課題基金的支持下，按照研究計畫中的研究內容和技術路線進行了四年的研究工作，取得了較好的研究成果。綜合四年來的工作，在本基金的資助下，我們在主要研究了若干難解問題的參數算法和核心化研究，並把參數計算理論套用於計算機網路、社會學和生物信息學中。在IEEE Transactions on Computers、Theoretical Computer Science、Journal of Combinatorial Optimization、 ESA、WADS、COCOON等期刊和會議上發表學術論文28篇。在參數算法研究中，主要研究了符號支配集問題參數算法、直角線段的路徑覆蓋問題、最大一致森林問題的參數算法、路徑覆蓋和星形覆蓋一棵樹問題和最大內部節點生成樹近似算法。對樹分解的符號支配集問題給出時間複雜度為O(k^k0.5)參數算法。對直角線段覆蓋問題給出大小為O((2d)k)的核，對最大一致森林問題分別為有根和無根的多顆二叉樹給出時間複雜度為O(3^k)和O(4^k)的算法，對於路徑覆蓋和星形覆蓋問題，分別給出時間複雜度為O((2+c)^k)和O(4^k)的參數算法，其中星形覆蓋的核為O(k^3)，最後對於最大內部節點生成樹，給出近似比為1.5的近似算法。本課題組還對其它一些NP難解問題的核心化及參數算法進行了研究，提出了若干有效的歸約規則和高效參數算法，例如加權3-set Packing、正負支配集和 P2-packing等問題。對於加權的3-set Packing給出了O(k^3)的核，對正負支配集問題給出一個亞指數的算法，以及P2-packing問題大小為O(k^2)的核和O(8^k)的參數算法。本課題組還將參數計算推廣到實際套用中，取得了一系類成果。針對感測器網路和社交網路中的難解問題進行了研究，如無線感測器網網路的Max- lifetime Target Coverage問題、d-approval規則投票系統等問題。對於Max- lifetime Target Coverage問題，證明了該問題是FPT的。針對d-approval規則投票系統問題，給出了大小為O(k^(d+2))的核。課題組在此方面的研究不僅推進了參數計算理論的發展，同時也推動了參數計算理論及技術在實際領域的套用。
