《難解問題的固定參數近似算法研究》是依託湖南師範大學，由劉運龍擔任項目負責人的面上項目。
基本介紹
- 中文名：難解問題的固定參數近似算法研究
- 項目類別：面上項目
- 項目負責人：劉運龍
- 依託單位：湖南師範大學
項目摘要,結題摘要,
項目摘要
固定參數近似算法採用參數計算方法尋求問題的近似解，是實際處理難解問題的一種新的有效手段。本項目深入地研究一系列NP-難解問題的固定參數近似算法，其目標是為固定參數可解問題尋求新的實用算法，為固定參數難解問題探索新的可解途徑。項目首先研究一些固定參數可解問題，提出具有適當近似率但時間複雜度比其固定參數精確算法明顯降低的固定參數近似算法。接著研究一批參數計算複雜性尚未定論或者為W[1]-難的問題，期待提出實際有效的固定參數近似算法。然後研究一些被猜測不存在固定參數近似算法的問題，力求從理論上證明其固定參數不可近似求解性。項目將多項式時間近似算法設計技術融合到參數計算方法，從拓展分支限界技術和非對稱性保真變換等不同角度探究固定參數近似算法設計新技術。本項目的研究為融合近似計算與參數計算兩類計算方法夯實理論基礎，為難解問題探索新的可解途徑創立實用方法。
結題摘要
在本基金的資助下，課題組對難解問題的固定參數近似算法進行了深入研究，並且取得了較大進展。研究內容既包括對同類問題固定參數近似算法設計的規律探究，又包括對一系列具體問題的算法研究；既包括對難解問題固定參數近似算法的研究，又包含對相關問題固定參數可解算法的研究；既注重對難解問題參數化算法的研究，又包含對相關圖類及其性質的研究。在同類問題固定參數近似算法設計技術的探究方面，課題組從固定參數可解問題、參數複雜性未定問題和W[t]-難解問題（t ≥1）三個方面分別探究了各類問題算法設計中的典型技術和一些具有規律性的方法。在具體問題的固定參數近似算法研究方面，課題組著重對Matching和Packing參數化計數問題進行了深入研究，首次證明了該類問題的計算複雜性是#W[1]-難的，同時對該類問題分別提出了固定參數可解的近似算法。在此基礎上，還分別研究了頂點互不相交的子圖Packing計數問題和邊互不相交的子圖Packing 計數問題，證明了前者的計算複雜性是#W[1]-難的，並對這兩類問題分別提出了固定參數可解的近似算法。在研究問題的固定參數可解算法方面，課題組研究了帶權的P3-Packing 問題、帶權的裝載著色問題和無鑽石圖上的Claw-free邊刪除問題等一系列難解問題，並運用隨機劃分方法分別對它們提出了固定參數隨機算法。這一方法也為研究相關問題的固定參數隨機近似算法打下基礎。在相關圖類及其性質研究方面，課題組研究了二部圖的關於加邊運算具有單調性結構參數的極值問題；研究了圖的連通度與單調性結構參數的極值問題；研究了四種基於圖笛卡爾積運算結構參數的算法問題；研究了兩個複雜網路的Tutte多項式。對這些問題取得了一系列重要研究結果。這些結果為進一步研究相關問題的固定參數近似算法奠定了新的理論基礎。項目的研究成果為一批NP難解問題提供了新的實際有效處理途徑，為它們在實際工程中的套用起到了促進作用。同時，研究成果豐富和發展了參數計算理論及技術。
