难解问题的固定参数近似算法研究

The fixed-parameter approximation algorithm applies the fixed-parameter approach to seek the approximation solution, and becomes one of practical approaches to deal with NP-hard problems. In this project, we will investigate the fixed-parameter approximation algorithms for series of NP-hard problems. The target is to present some novel practical algorithms for the fixed-parameter tractable problems and explore a new tractable approach for the fixed-parameter intractable problems. More specially, we first study several fixed-parameter tractable problems and present some fixed-parameter approximation algorithms for them respectively, which output the approximation solution with proper approximation ratio but admit more significant decreased running time than that of the fixed-parameter exact algorithms. Then, we study series of problems, for which the parameter computational complexity is open or W[1]-hard , and explore fixed-parameter approximation algorithms for them respectively. In addition, we try to prove the fixed-parameter inapproximability for some problems that are conjectured not admitting fixed-parameter approximation algorithms. In the research process, we will combine several techniques used in polynomial-time approximation algorithms with that in fixed-parameter algorithms, and explore the new techniques for designing the fixed-parameter approximation algorithms along different lines, such as extending branching-and-searching, problem transformation via fidelity preserving reduction. Our research will greatly extend the theoretical foundation on the combination both the polynomial-time approximation approach and the fixed-parameter approach, and provide more utility methods on exploring tractable approaches for the NP-hard problems.

固定参数近似算法采用参数计算方法寻求问题的近似解，是实际处理难解问题的一种新的有效手段。本项目深入地研究一系列NP-难解问题的固定参数近似算法，其目标是为固定参数可解问题寻求新的实用算法，为固定参数难解问题探索新的可解途径。项目首先研究一些固定参数可解问题，提出具有适当近似率但时间复杂度比其固定参数精确算法明显降低的固定参数近似算法。接着研究一批参数计算复杂性尚未定论或者为W[1]-难的问题，期待提出实际有效的固定参数近似算法。然后研究一些被猜测不存在固定参数近似算法的问题，力求从理论上证明其固定参数不可近似求解性。项目将多项式时间近似算法设计技术融合到参数计算方法，从拓展分支限界技术和非对称性保真变换等不同角度探究固定参数近似算法设计新技术。本项目的研究为融合近似计算与参数计算两类计算方法夯实理论基础，为难解问题探索新的可解途径创立实用方法。

在本基金的资助下，课题组对难解问题的固定参数近似算法进行了深入研究，并且取得了较大进展。研究内容既包括对同类问题固定参数近似算法设计的规律探究，又包括对一系列具体问题的算法研究；既包括对难解问题固定参数近似算法的研究，又包含对相关问题固定参数可解算法的研究；既注重对难解问题参数化算法的研究，又包含对相关图类及其性质的研究。. 在同类问题固定参数近似算法设计技术的探究方面，课题组从固定参数可解问题、参数复杂性未定问题和W[t]-难解问题（t ≥1）三个方面分别探究了各类问题算法设计中的典型技术和一些具有规律性的方法。在具体问题的固定参数近似算法研究方面，课题组着重对Matching和Packing参数化计数问题进行了深入研究，首次证明了该类问题的计算复杂性是#W[1]-难的，同时对该类问题分别提出了固定参数可解的近似算法。在此基础上，还分别研究了顶点互不相交的子图Packing计数问题和边互不相交的子图Packing 计数问题，证明了前者的计算复杂性是#W[1]-难的，并对这两类问题分别提出了固定参数可解的近似算法。. 在研究问题的固定参数可解算法方面，课题组研究了带权的P3-Packing 问题、带权的装载着色问题和无钻石图上的Claw-free边删除问题等一系列难解问题，并运用随机划分方法分别对它们提出了固定参数随机算法。这一方法也为研究相关问题的固定参数随机近似算法打下基础。. 在相关图类及其性质研究方面，课题组研究了二部图的关于加边运算具有单调性结构参数的极值问题；研究了图的连通度与单调性结构参数的极值问题；研究了四种基于图笛卡尔积运算结构参数的算法问题；研究了两个复杂网络的Tutte多项式。对这些问题取得了一系列重要研究结果。这些结果为进一步研究相关问题的固定参数近似算法奠定了新的理论基础。. 项目的研究成果为一批NP难解问题提供了新的实际有效处理途径，为它们在实际工程中的应用起到了促进作用。同时，研究成果丰富和发展了参数计算理论及技术。