3-Set Packing参数化计数问题的复杂性及近似算法

Set Packing参数化计数问题即在一个3-Set Packing实例中统计所有大小为k的不同packing的个数。首先证明了该问题的计算复杂性是#W[1]-难的,表明该问题不大可能存在固定参数可解的精确算法(除非#W[1]=FPT)。然后,通过拓展3-D Matching参数化计数问题的算法对3-Set Packing参数化计数问题提出了一个基于Monte-Carlo自适应覆盖算法和着色技术的随机近似算法。     

Set Packing问题的研究进展

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

基于Level Set方法的人脸轮廓提取

人脸轮廓提取在诸如安全检查,保安管理、交通电子监控、机器人研究等方面有着十分重要的应用价值.先利用图像背景差分法快速检测出人脸的初始矩形轮廓线,然后采用Level Set方法对视频图像进行人脸轮廓提取,Level Set演化函数空间方向上采用四阶紧致差分逼近式离散,计算过程中加入了窄带算法和全局优化方法.数值实验结果表明,该算法在不增加计算时间的基础上,可以检测出模糊或离散的边界,并得到精确的人脸轮廓线.     

基于Rough Set的空间数据分类方法

近来,数据采掘的研究已从关系型和事务型数据库扩展到空间数据库.空间数据采掘是一个很有发展前景的领域,其中空间数据分类的研究尚处在起步阶段.该文分析和比较了现有的几个空间数据分类方法的利和弊,提出利用Rough Set的三阶段空间分类过程.实验结果表明,该算法对于解决包含不完整空间信息的问题是有效的.     

基于Level Set方法的点采样曲面测地线计算及区域分解

点采样物体的几何处理是当前造型领域中的研究热点之一,如何有效地对点采样曲面进行区域分解是几何处理的基础性工作．该文首先提出了一种基于Level Set方法的点采样曲面上两点间最短路径的计算方法,用以解决区域分解中的边界曲线生成问题．为了保证求解Level Set微分方程的稳定性,文章采用移动最小平方(MLS)方法对点采样曲面进行均匀重采样和去噪音处理．在此基础上,又进一步提出了一个基于Level Set方法的点采样曲面区域拾取算法．最后给出了上述算法在点采样物体的几何处理中的应用实例．实验结果表明该文提出的算法稳定、快速且容易实现。     

一类弱集合覆盖问题的近似算法

在近似算法领域,集合覆盖（Set Cover）是研究的比较早和比较透彻的问题之一．该文提出了一类与集合覆盖很相似的问题：集合击中和弱集合b-覆盖,并且给出了解决它们的近似算法,还证明了它们的不可近似性．     

基于Rough Set的电子邮件分类系统

随着电子邮件的广泛使用，通过它进行不良信息传播的事件不断发生，电子邮件分类问题成为了网络安全研究的热点。本文通过对电子邮件头进行分析，运用Rough Set理论中相关的数据分析技术，建立了电子邮件分类系统的模型，并进行了实验测试，得到了满意的结果。     

基于Rough Set理论的一种属性值约简算法

属性值的约简是Rough Set理论的核心内容之一。它的口的就是在保持规则集的分类能力的条件下，删除多余属性值，进一步简化规则集。从而，得到最小的知识库。本文针对Rough Set理论中值约简这个重要问题进行了研究，提出了一种利用决策规则质量的属性值约简算法。该算法比现有的值约简算法更简化，并用实验证明了其有效性。     

基于Rough Set的属性约简及应用研究

设计简洁的切实可行的基于Rough Set的属性约简的算法.通过基于Rough Set的属性约简方法对两个实际应用说明了如何利用该方法计算条件属性相对于决策属性的重要度,去除冗余属性,形成新的精简的知识发现属性集,从而提高数据挖掘效率.     

基于Rough Set的规则自动抽取设计方案

知识获取是专家系统的重要研究领域，而Rough Set理论以理论的独特之处成为这一领域的有效工具。文章针对一具体专家系统－OTCA－ES专家系统－在知识获取方面能力的不足，简要介绍其知识表示和知识获取的方法后，提出了一种基于Rough Set理论的规则自动抽取的设计方案。     

反馈集问题的研究进展

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。     

测试集问题的集合覆盖贪心算法的深入近似

测试集问题是一个有着广泛应用的NP难问题.集合覆盖贪心算法是测试集问题的一个常用近似算法,其由集合覆盖问题得到的近似比21nn+1能否改进是一个公开的问题.集合覆盖贪心算法的推广被用来求解生物信息学中出现的冗余测试集问题.通过分析条目对被区分次数的分布情况,用去随机方法证明了集合覆盖贪心算法对测试集问题的近似比可以为1.51nn+0.5lnlnn+2,从而缩小了这种算法近似比分析的间隙.另外,给出了集合覆盖贪心算法对冗余度为n-1的加权冗余测试集问题的近似比的紧密下界(2-o(1))lnn-Θ 1).     

Set Constraints with Intersection

Set constraints are inclusions between expressions denoting sets of trees. The efficiency of their satisfiability test is a central issue in set-based program analysis, their main application domain. We introduce the class of set constraints with intersection (the only operators forming the expressions are constructors and intersection) and show that its satisfiability problem is DEXPTIME-complete. The complexity characterization continues to hold for negative set constraints with intersection (which have positive and negated inclusions). We reduce the satisfiability problem for these constraints to one over the interpretation domain of nonempty sets of trees. Set constraints with intersection over the domain of nonempty sets of trees enjoy the fundamental property of independence of negated conjuncts. This allows us to handle each negated inclusion separately by the entailment algorithm that we devise. We furthermore prove that set constraints with intersection are equivalent to the class of definite set constraints and thereby settle the complexity question of the historically first class for which the decidability question was solved.     

隐私保护集合交集计算协议

隐私保护集合交集计算属于安全多方计算领域的特定应用问题,具有重要的研究价值和广泛的应用范围。在信息高速发展的时代,对该问题的研究满足了人们在日常生活中享受各种便利的同时隐私得到保护的需求。文章考虑的是两个参与者隐私保护集合交集计算的情形,首先将集合表示成多项式,把求解两个集合的交集问题转化为求解两个多项式的最大公因式问题;在此基础上,根据多项式的数学性质和Pailliar同态加密算法提出一种保护隐私的两方集合交集计算协议,并给出协议的正确性和安全性分析;最后通过与相关文献的比较分析,得出文章协议的计算复杂度和通信复杂度较低的结论,且能够很好地保护参与方集合的元素个数。     

The Feedback Arc Set Problem with Triangle Inequality Is a Vertex Cover Problem

We consider the (precedence constrained) Minimum Feedback Arc Set problem with triangle inequalities on the weights, which finds important applications in problems of ranking with inconsistent information. We present a surprising structural insight showing that the problem is a special case of the minimum vertex cover in hypergraphs with edges of size at most 3.     

基于动态极大度的极小碰集求解方法

在计算集合簇的碰集时,结合SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好.     

一种融合实体语义知识的实体集合扩展方法

实体集合扩展是开放式信息抽取的一个重要问题,该问题研究如何从一个语义类的若干实体(称为种子)出发,得到该类别的更多实体。现有实体集合扩展方法主要使用上下文模板或种子在语料中的分布信息进行抽取,其缺点是无法解决种子的歧义问题,而该问题会影响方法的有效性。在该文中,作者提出了一种融合实体语义知识的实体集合扩展方法,通过引入语义知识来解决种子歧义性问题。新方法通过使用Wikipedia实现了语义知识的引入,并把基于语义知识的扩展方法和基于模板的扩展方法相融合。实验表明,与单纯基于上下文方法相比,该文方法在准确率上提升了18.5%,召回率上提升了6.8%,MAP值上提升了22.8%。     

On the Positive-Negative Partial Set Cover problem

The Positive-Negative Partial Set Cover problem is introduced and its complexity, especially the hardness-of-approximation, is studied. The problem generalizes the Set Cover problem, and it naturally arises in certain data mining applications.     

Molecular solutions for minimum and exact cover problems in the tile assembly model

The tile assembly model is a novel biological computing model where information is encoded in DNA tiles. It is an efficient way to solve NP-complete problems due to its scalability and parallelism. In this paper, we apply the tile assembly model to solve the minimum and exact set cover problems, which are well-known NP-complete problems. To solve the minimum set cover problem, we design a MinSetCover system composed of three parts, i.e., the seed configuration subsystem, the nondeterministic choice subsystem, and the detection subsystem. Moreover, we improve the MinSetCover system and propose a MinExactSetCover system for solving the problem of exact cover by 3-sets. Finally we analyze the computation complexity and perform a simulation experiment to verify the effectiveness and correctness of the proposed systems.