若干NP難解問題的參數化算法研究.pdf

1、NP難解問題是理論計算機科學的主要研究對象,對NP難解問題提出實際有效的固定參數可解算法是理論計算機科學中的一個新的研究方向。
　　 本文以Matching、Packing、Maximum Cut和MultiCut等經典的NP難解問題為研究對象,在深入挖掘問題結構中新特點、新性質的基礎上,運用多種參數計算技術對它們提出了一系列的固定參數可解算法。其主要研究工作包括:
　　 帶權的m-Set Packing、m-D Mat

2、ching問題以前一直是用近似算法求解的,本文運用參數計算理論對該類問題進行了研究,首次證明了該類問題是固定參數可解的。本文首先運用最新的著色技術和動態規劃技術對帶權的m-Set Packing問題提出了一個時間復雜度為O(12.2mknO(1)的固定參數可解算法,接著在此基礎上利用問題本身的結構特點對帶權的m-D Matching問題提出了一個時間復雜度為O(12.2(m-1)knO(1)的固定參數可解算法,然后對帶權的3-D Mat

3、ching問題提出了一個時間復雜度為D(5.483k2z)的固定參數枚舉算法,其中z表示需要枚舉的權值最優解的個數。
　　 針對3-D Matching參數化計數問題目前還不存在固定參數可解的精確算法,本文提出了一個基于Monte-Carlo自適應覆蓋算法的固定參數可解隨機近似算法。即對于一個含有n個三元組的集合S,給定一個整數k和兩個正實數ε和δ,該算法能在時間O(5.483kn21n(2/δ)/ε2)內返回一個數N,使得Pr

4、ob[(1-ε)No≤(1+ε)N0]≥1-δ,其中N0表示S中大小為k的matching的精確個數。在設計該隨機近似算法時,本文的關鍵發現是3-D Matching參數化計數問題通過著色技術可以轉化為標準的集合并集計數問題。
　　 Maximum Cut問題通常是用近似算法來求解的,本文運用參數計算理論對該問題進行了研究。首先對該問題及其相關概念進行了參數化定義,然后對參數化Maximum Cut問題提出了一種基于隨機劃分技術

5、的隨機算法。該隨機算法依次將實例圖的頂點進行[1n(1/ε)]×2k(0<ε＜1)次隨機劃分,并選擇其中權值最大的k-劃分作為輸出解,因而能在時間O*(1n(1/ε)2k)內以至少1-ε的概率找到目標解。接著在此基礎上運用最新改進的(n,k)-全集劃分技術對參數化Maximum Cut問題提出了一個時間復雜度為O*(22k+12log2(2k)的確定性算法,表明了Maximum Cut問題是固定參數可解的。
　　 本文進一步研究

6、了基于保證值參數化MaxCut問題的核和算法,并得到了相關改進結果。對關于頂點的核提出了一個√8k的下界,將關于邊的核由16k2-18k+6減少至8k2+10k+2,并且在此基礎上將求解該問題當前最好算法的時間復雜度由O*(16k)改進至O*(8.999k)。
　　 本文還進一步研究了MultiCut問題,并對它提出了一個新的參數化算法。在深入分析問題結構特點的基礎上,本文運用集合劃分策略和相關問題的最新研究結果對MultiCu