不可近似性相关论文
本文研究了一个属于图论领域的优化问题，即MaximumSimpleSharing(MSS)问题。MsS问题的目标，是在一个二分无向图上寻找由互不相交的路......
在已知边带权的连通图中找一棵边权总和最小的生成树的问题很早就被提出和研究[15，14】，并且也得到了广泛的应用【15，14，23】。但是在......
在本文中，我们将考虑如下三个在网络设计中抽象出来的优化问题，一是内点带权最小生成树问题，二是多商品设备选址问题，三是多层次设备选......
从90年代初开始,随着人类基因组计划的展开与深入,科学工作者发现,人类的各种遗传、性状和甚至疾病等都与基因有着密切的联系。基......
本文研究的是一类调整和-费用向量时的极大+和支撑树逆问题(IMSST).极大+和支撑树问题(MSST)是在一个边赋权无向连通网络G(V,E，c，w)......
PCP定理是近十年来计算复杂性领域内的重要成果之一,介绍了从图灵计算模型到概率可验证明（PCP）计算模型的演变过程、PCP系统的基本理......
图模型概率推理的主要任务是通过对联合概率分布进行变量求和来计算配分函数、变量边缘概率分布、条件概率分布等。图模型概率推理......
最大圈分解问题最早由Erd6s和Pbsa提出，随后研究人员在图论领域和理论计算机科学领域中对其进行了广泛的探索。最近研究发现，该问题......
通过一个适当的归约变换，可以将一个CNF（conjunctive normal form）公式变换为另一个具有某种特殊结构或性质的公式，使两者具有相同的可......
假设有p台计算机，n张载有信息的网页，其各网页的长度都与计算机和时间有关，现在的问题是，求一个安排．使这p台计算机能在最短的时间内下......
以线性规划(linear program,LP)对非确定多项式(Non-Deterministic Polynomial,NP)问题的近似求解算法进行了讨论。首先,介绍了LP......
对有限个固定工件,n个自由工件的单机排序问题1｜FB（F）｜max wjCj进行了研究,证明该问题在F≥2的情况下不存在最坏性能比为2n的多项式时......
标准近似、微分近似和占优分析是三种不同的近似算法度量方法。标准近似比度量近似解偏离最优解的相对误差。微分近似关注近似解解......
圈问题是图论、组合优化、运筹学、数理经济学以及理论计算机科学中的重要研究对象。本文的研究围绕旅行商问题和最大覆盖圈包装问......
