Set Packing问题的研究进展

Set Packing问题起源于分割问题的应用,是在强约束条件对元素进行划分。在复杂性理论中,此问题是一类重要的NP难问题,被广泛应用于调度、代码优化和生物信息学等领域。特别是在参数计算理论产生后,此问题再次成为研究的热点问题。依据所研究问题的差异,本文将Set Packing问题分成5类,并给出了具体的定义。在此基础上,分别介绍了求解这5类问题的相关算法,着重分析和比较了参数算法中所运用的各项技术,并提出了该问题算法研究的一些发展方向。     

彩色编码技术的研究进展及应用

作为一种重要的参数化技术,彩色编码技术得到了越来越多的重视并在近年来取得了理论和应用上的一系列进展.本文首先介绍了彩色编码技术的基本思想和相关定义,并详细论述了随机式和确定式两种彩色编码技术.最后本文具体介绍和分析了彩色编码技术在路径查找、子图同构、matching与packing、(t,n)-环签名等问题上的应用,并探讨了彩色编码技术及其应用的进一步研究工作.     

虚拟网映射问题的计算复杂性分析

虚拟网映射是实现网络虚拟化的关键环节,其任务是在满足虚拟网构建约束的前提下,把虚拟网的虚拟节点和虚拟链路分别映射到底层物理网的节点和路径上。文中根据虚拟节点映射是否已知、物理网是否支持路径分割、物理节点是否支持重复映射等特征,对虚拟网映射问题进行分类,并针对一般网络拓扑模型和某些特殊网络拓扑模型完成各类虚拟网映射可行问题和优化问题的计算复杂性分析。     

网树求解有向无环图中具有长度约束的简单路径和最长路径问题

具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs,NSPLCDAG).网树是一种多树根多双亲的数据结构.NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对NSPLCDAG算法进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法(Nettree for the Longest Path in DAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.     

寻找图中两顶点间最长路径的算法设计

在"图"这种数据结构中,求解任意两顶点之间最长路径算法,有着广泛的理论和应用背景,而其求解算法却研究较少,没有像求解最短路径算法那样有成熟的算法(Dijkstra算法和Floyd算法[1])和广泛的影响.讨论并实现了一种查找图中任意两顶点间带权路径长度中最长路径的算法.使用该算法可以回答图中任意两个顶点之间的最长路径长度及任意两顶点间存在的不同路径的数目.     

可满足性问题的研究综述

对SAT问题及其各种约束子问题进行分类并给出具体定义,着重介绍常规SAT问题、最大可满足性问题（MAX—SAT）和参数化SAT问题的相关算法,并对参数算法中运用的技术进行分析和比较,提出一些SAT问题研究中值得关注的几个方面。     

物流配送中双向车辆路径问题(VRP)的研究

本文在原有的车辆路径问题单一目标模型的基础上提出了满足多目标车辆路径问题的数学模型,并提出带回收的vrp案例,用新的Clarke-Wright方法加以解决。     

基于改进的蜂群算法求解专有路径保护设计优化问题

针对光网络故障恢复资源利用的优化问题,采用改进的蜂群算法（IABC）来求解专有路径保护设计优化问题。由于采蜜机理的蜂群算法全局寻优能力较弱,引入禁忌表机制,增强算法搜索全局最优解的能力,并改进蜂群算法的交叉算子,增强算法的收敛速度。通过实验仿真。结果表明与传统的ABC算法相比,IABC能算法大大地提高计算效率,针对较复杂网络资源优化的NP问题提供有效的可行性实施方法。     

求解卸装一体化的车辆路径问题的混合启发式算法

提出一种结合蚁群系统(Ant Colony System,ACS)和变邻域下降搜索(Variable Neighborhood Descent,VND)的混合启发式算法ACS_VND,求解卸装一体化车辆路径问题.利用基于插入的ACS解构造方法产生多个弱可行解,再逐个转换成强可行解,并选择其中最好的作为VND的初始解.在VND过程中使用三种不同的邻域结构:插入、交换和2-opt依次对解进行迭代优化.对55个规模为22~199的benchmark算例的求解结果表明,算法ACS_VND能在较短时间内获得52个算例的已知最好解,并且更新了其中44个算例的已知最好解,求解性能优于现有算法.     

有不同中断时间代价的一致并行抢先调度问题

提出了具有不同中断时间代价的抢先调度问题(P|ptmn(δi)|Cmax)．该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景．首先证明了这个问题是一个NP难优化问题．并给出了一个时间复杂度为O(nlogn)的近似算法,其近似度为5／3．算法的特点是结合中断时间δi来应用LPT思想,而不只是把它应用到任务i的执行时间pi上,从而避免了LPT算法在最坏情形下的近似度差的问题．在算法的关键部分,运用了均分的技巧来提高任务执行的并行性,进一步提高了近似度．     

On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems

We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1]=FPT, this rules out the existence of algorithms with time complexity of O(f(k)nα) for those problems. Here n is the size of the problem instance, α is constant, k is the number of strings and f is any function of k. The fixed alphabet version of the LCS problem is of particular interest considering the importance of sequence comparison (e.g. multiple sequence alignment) in the fixed length alphabet world of DNA and protein sequences.     

无向连通图中求约束条件下近似最长路算法

在无向连通图中寻找最长路是一个NP问题,在实际应用中往往以近似最长路来代替最长路,但现存的算法都针对图中任意两点之间的近似最长路。该文利用一条最长路中是不可以被再插入一个新顶点的这个事实,通过对图的深度优先生成树的指定起点和终点之间的路径进行不断插入的方法,以多项式的算法复杂度求得一条指定起点和终点间不可再被插入顶点的路,而这样的一条路往往非常接近指定的起点与终点之间的最长路。该算法在绣花打版软件的应用中取得了良好的效果。     

Beam search for the longest common subsequence problem

The longest common subsequence problem is a classical string problem that concerns finding the common part of a set of strings. It has several important applications, for example, pattern recognition or computational biology. Most research efforts up to now have focused on solving this problem optimally. In comparison, only few works exist dealing with heuristic approaches. In this work we present a deterministic beam search algorithm. The results show that our algorithm outperforms the current state-of-the-art approaches not only in solution quality but often also in computation time.     

Chordless paths through three vertices

Consider the following problem, which we call “Chordless path through three vertices” or CP3V, for short: Given a simple undirected graph G=(V,E)$G=(V,E)$, a positive integer k, and three distinct vertices s, t  , and v∈V$v\in V$, is there a chordless path of length at most k from s   via v$v$ to t in G? In a chordless path, no two vertices are connected by an edge that is not in the path. Alternatively, one could say that the subgraph induced by the vertex set of the path in G is the path itself. The problem has arisen in the context of service deployment in communication networks. We resolve the parametric complexity of CP3V by proving it W[1]$W[1]$-complete with respect to its natural parameter k  . Our reduction extends to a number of related problems about chordless paths and cycles. In particular, deciding on the existence of a single directed chordless (s,t)$(s,t)$-path in a digraph is also W[1]$W[1]$-complete with respect to the length of the path.     

Parameterized complexity and improved inapproximability for computing the largest j-simplex in a V-polytope

We consider the problem of computing the squared volume of the largest j-simplex contained in an n-dimensional polytope presented by its vertices (a V-polytope). We show that the related decision problem is W[1]-complete, with respect to the parameter j. We also improve the constant inapproximability factor given in [A. Packer, Polynomial-time approximation of largest simplices in V-polytopes, Discrete Appl. Math. 134 (1-3) (2004) 213-237], by showing that there are constants μ<1,c>1 such that it is NP-hard to approximate within a factor of cμn the volume of the largest ⌊μn⌋-simplex contained in an n-dimensional polytope with O(n) vertices.