论文部分内容阅读
NP难解问题是理论计算机科学的主要研究对象,对NP难解问题提出实际有效的固定参数可解算法是理论计算机科学中的一个新的研究方向。本文以Matching、Packing、Maximum Cut和MultiCut等经典的NP难解问题为研究对象,在深入挖掘问题结构中新特点、新性质的基础上,运用多种参数计算技术对它们提出了一系列的固定参数可解算法。其主要研究工作包括：带权的m-Set Packing、m-D Matching问题以前一直是用近似算法求解的,本文运用参数计算理论对该类问题进行了研究,首次证明了该类问题是固定参数可解的。本文首先运用最新的着色技术和动态规划技术对带权的m-Set Packing问题提出了一个时间复杂度为O(12.2mknO(1))的固定参数可解算法,接着在此基础上利用问题本身的结构特点对带权的m-D Matching问题提出了一个时间复杂度为O(12.2(m-1)knO(1))的固定参数可解算法,然后对带权的3-D Matching问题提出了一个时间复杂度为O(5.483kn2z)的固定参数枚举算法,其中z表示需要枚举的权值最优解的个数。针对3-D Matching参数化计数问题目前还不存在固定参数可解的精确算法,本文提出了一个基于Monte-Carlo自适应覆盖算法的固定参数可解随机近似算法。即对于一个含有n个三元组的集合S,给定一个整数k和两个正实数ε和δ,该算法能在时间O(5.483kn2ln(2/δ)/ε2)内返回一个数N,使得Prob[(1-ε).N0≤N≤(1+ε)N0]≥1-δ,其中N0表示S中大小为k的matching的精确个数。在设计该随机近似算法时,本文的关键发现是3-D Matching参数化计数问题通过着色技术可以转化为标准的集合并集计数问题。Maximum Cut问题通常是用近似算法来求解的,本文运用参数计算理论对该问题进行了研究。首先对该问题及其相关概念进行了参数化定义,然后对参数化Maximum Cut问题提出了一种基于随机划分技术的随机算法。该随机算法依次将实例图的顶点进行[ln(1/ε)]×2k(0＜ε＜1)次随机划分,并选择其中权值最大的k-划分作为输出解,因而能在时间O*(ln(1/ε)2k)勺内以至少1-ε的概率找到目标解。接着在此基础上运用最新改进的(n,k)-全集划分技术对参数化Maximum Cut问题提出了一个时间复杂度为O*(22k+12log2(2k))的确定性算法,表明了Maximum Cut问题是固定参数可解的。本文进一步研究了基于保证值参数化MaxCut问题的核和算法,并得到了相关改进结果。对关于顶点的核提出了一个(?)的下界,将关于边的核由16k2-18k+6减少至8k2+10k+2,并且在此基础上将求解该问题当前最好算法的时间复杂度由O*(16k)改进至O*(8.999k)。本文还进一步研究了MultiCut问题,并对它提出了一个新的参数化算法。在深入分析问题结构特点的基础上,本文运用集合划分策略和相关问题的最新研究结果对MultiCut问题提出了一个时间复杂度为O*([(?)]2l4k)勺的参数化算法,其中l为给定的顶点对数目,k为需删除的顶点个数。该算法明显地改进了当前时间复杂度为O*(2klkk4k3)的最好算法。