分层算法求解竞赛图上的最小弱顶点覆盖

竞赛图上的弱顶点覆盖问题是一个NP困难问题,本文先定义了竞赛图上的势加权函数,然后利用分层技术给出了一个求解竞赛图最小弱顶点覆盖问题的近似算法,并证明了此近似算法的近似度为3     

奖励收集顶点覆盖问题的一个2-近似算法

给定图G、点赋权函数c和边惩罚费用w,对于图中任一顶点子集FV,F的权重可定义为其包含的顶点权重之和加上图G中未被其覆盖的边的费用之和。如何寻找一个权重最小的顶点子集F是近年来研究者广泛关注的问题之一。这一问题被称作奖励收集顶点覆盖问题。本文采用迭代松弛方法给出了这一问题的一个近似算法,并证明了该算法的近似度为2。     

求一般图的最小顶点覆盖集问题的混合贪婪算法

现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大.根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法.该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为O(|V|2),执行效果较好,性能近似比不大于4/3,接近已知的可能的近似比下界1.166 6,低于2005年认为最低的近似比1.361,是图的最小顶点覆盖问题算法的一个较好的补充.     

基于邻接矩阵的网络流量检测点选取算法研究

为对网络流量进行有效检测,考虑网络节点的流守恒,把网络流量检测点选取问题抽象为无向图的弱顶点覆盖问题.基于图论中邻接矩阵的概念,在满足对任意顶点度数大于2的假设条件下,提出一个求解弱顶点覆盖问题的近似算法.通过将求解弱顶点覆盖集中点与边的关系转化为点与点的关系,降低了矩阵计算复杂度.仿真实验表明,与现有算法相比,新算法能够选取出更小的弱顶点覆盖集,部署更少的网络流量检测点,减轻了由网络流量数据收集造成的额外负担.     

逼近4正则图的最小顶点覆盖问题的难解性(英文)

证明了逼近4正则图的最小顶点覆盖问题在某个常数因子内是计算难解的.相似地,对于5正则图、6正则图等的最小顶点覆盖问题,这个结论也成立.已知逼近3正则图的最小顶点覆盖问题在某个常数因子内是计算难解的,文章扩展了这个结果到4正则图情况,用K-归约证明这个结果,给出了一个从3正则图的最小顶点覆盖问题到4正则图的最小顶点覆盖问题的K-归约.     

最小顶点覆盖问题的一个近似算法

最小顶点覆盖是图论中的一个重要概念，它是一个NP难的问题．给出了一个求解最小顶点覆盖的近似算法，与现有算法相比具有更优的性能比。     

带线性惩罚的次模边点控制集问题的近似算法

考虑带线性惩罚的次模边点控制集问题，给定一个无向图G=(V,E),且V中每个顶点都有一个非负惩罚，E的每个边子集都有一个非负权值.称e={u,v}∈E为边点控制顶点w,如果w∈N[u]∪N[v],这里N[u],N[v]分别为顶点u,v的闭邻域.带线性惩罚的次模边点控制集问题的目标是寻找一个边子集D,使得D的权值与未被D边点控制的顶点的惩罚费用之和最小.利用原始对偶技巧给出此问题的一个k-近似算法，其中k=max_v∈V|N[v]|.     

基于DNA自组装模型解决图的最小顶点覆盖问题

在分析最小顶点覆盖问题特点的基础上,以5个顶点的图为例,将最小顶点覆盖问题转化为可满足性问题,简化问题的操作难度。再根据DNA自组装的自发性和并行性等优势,通过建立DNA自组装模型解决可满足性问题,从而解决图的最小顶点覆盖问题。相对于传统算法,本算法只应用了凝胶电泳技术,大大的降低了操作难度和误差。     

Pythagorean模糊信息系统属性约简的图论方法

信息系统中,属性约简是知识发现问题的一个研究热点,能达到发掘并简化知识的目的。目前已有很多利用辨识矩阵来进行属性约简的研究,但是当数据维数较大时,算法复杂度往往很大。利用加权欧几里得距离来定义二元关系及辨识矩阵,利用信息系统的约简与生成图的最小顶点覆盖等价的关系,将辨识矩阵求解约简的问题转化为求解生成图中最小顶点覆盖的问题,并给出了Pythagorean模糊信息系统中属性约简的算法;在此基础上,利用基于加权欧几里得距离的相似关系,定义了Pythagorean模糊决策信息系统的辨识矩阵,并给出了用最小顶点覆盖的方法求约简算法,最后利用实例验证了算法的有效性。     

基于稀疏优化模型的网格逼近

提出了一种新的基于稀疏优化的网格逼近方法,使得三维几何物体可以由用户指定的合理的面片数的平面多边形来近似表示.该方法首先对输入的三维网格的面片法向进行L_0模优化,然后根据优化后的面片法向信息来驱动顶点位置更新.其次,对现有模型进行面片聚类.最后提出了一个基于全局顶点的稀疏优化模型.通过约束聚类边界顶点梯度L_0模最小对网格进行平面多边形逼近.大量的网格简化结果证明了所提出的优化模型与方法的有效性以及稳定性.     

一种求解下模集函数最大值问题的近似算法

下模集函数最大值问题属于NP-难问题,难以得到有效的求解方法。针对这一情况,运用概率分布方法,给出了求解该问题的一种近似算法,并证明算法的性能保证为1／3。组合优化问题实例证明了该算法的有效性。该研究可为求解下模集函数最大值问题提供新的思路。     

最大化非减次模集函数问题的近似算法及其性能保证

次模集函数的最值问题在组合优化问题中有广泛应用,次模集函数的增减性对该问题的分析具有一定的简化作用．给出了求解非减次模集函数最大值问题的一种近似算法,并讨论了所给算法的性能保证．     

求解组合拍卖问题最大值的贪婪算法

为有效解决组合拍卖问题,从基约束条件下,下模函数最大值问题的基本结论出发,逐步过渡到求解组合拍卖问题的贪婪算法,给出一种新的近似算法,分析了该算法的性能保证.该算法是一种改进的贪婪算法,即将部分穷举法与贪婪算法结合,从而使其具有更好的性能保证,并从理论上证明了该算法的可靠性和有效性.     

关于满Steiner树问题的一个近似算法

满Steiner树问题(TST)是求解一个正则点都是叶子的最小Steiner树问题.Fabio Viduani Martinez等人给出了此问题的近似算法,它的性能比为2ρ-ρ/(3ρ-2)≈2.52,而目前求解Steiner树问题的近似算法的性能比,最小值约为1.550.对满Steiner树问题给出了一个近似算法,并将它的性能比改进为2ρ-3ρ/(6ρ-2)≈2.463.     

最大一致流问题的一个逼近算法

通过建构辅助网络，以K0ne和Vygen于2000年所给出的一个求最大多种物资网络流问题的逼近解的完全多项式算法作为子程序进行二分搜索，给出了一个新的求解最大一致流问题的逼近算法．然后，进行算法分析，说明了所建立的算法是拟多项式算法，并且给出与证明了一个有关输出的流与输入问题的解之间的逼近关系．该项工作表明从一个多种物资网络流问题的算法出发通过变换求解其他有关问题是可行的，并且为研究网络流问题提供了一种新的方法．     

求解机会约束优化的Log-Sigmoid近似问题的样本均值近似方法

样本均值近似(SAA)方法在机会约束优化问题中扮演着重要的角色.基于机会约束优化问题的Log-Sigmoid近似,探讨求解Log-Sigmoid近似问题的样本均值近似方法.构造了约束函数的样本均值近似函数,建立了相应的样本均值近似问题,并且证明当样本数量足够大时,样本均值近似问题的最优值和最优解集分别以概率为1收敛于Log-Sigmoid近似问题的最优值和最优解集.     

变分不等式有限元逼近的并行Schwarz算法

讨论了单障碍问题有限元逼近的并行Ｓｓｈｗａｒｚ算法，建立了与吕涛的算法等价的实用算法，并说明了其收敛性，同时讨论了该处对于贴合于分量有有限步收敛性。     

反自反矩阵的广义逆特征值问题

研究了反自反矩阵的广义逆特征值问题及其最佳逼近。得到了广义逆特征值问题解的一般表达式,对于任意给定的n阶复矩阵对（A~＊,B~＊）,得到了最佳逼近解,并给出了相应的算法及数值例子。     

超图嵌入带权重圈的一个2-近似算法

超图嵌入带权圈(HEWC)问题就是把超图的超边以路的形式嵌入一个带权圈, 使得圈上任何带权连接边的最大阻塞最小。这个问题的一个简单形式是图嵌入带权圈(GEWC),即把普通图的边以路的形式嵌入 一个带权圈。HEWC问题第一次被归结为一个整数线性规划问题,并且利用LP的放松问题和有界启发得到一个近似解。 然后设计了一个非常简单有用的可以和LP近似算法得到一样好的近似解的线性时间近似算法。     

二值和多值图象的边界跟踪及逼近

对二值和多值图象的边界跟踪和逼近问题作了探讨；提出了可识别边界线上左右边缘点的边界跟踪算法、利用链码的矢量性的多边形逼近算法和二次Ｂｅｚｉｅｒ曲线逼近算法。这些算法简单实用，效果较好。