【摘 要】
：
二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,
论文部分内容阅读
二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为：当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖（ku,kl）时,对任意给定的近似率δ=1＋ε〉1,一定可以找到一个受约束近似点覆盖（ku,kl）,对应的近似率为max{ku^＊/ku,kl^＊/kl}≤1＋ε,整个近似算法的运行时间复杂度为O（22/ε）。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案
其他文献
复杂装备研制过程中，上级供应商往往采取对下级供应商的扶持的做法，基于此，构建了一类基于多级递阶规划的复杂装备研制质量协商模型，分析了质量指标递阶分解和质量协商递阶规划流
提出了一种带有指导信息的k-means方法多支持向量机（SkSVM）。带有指导信息的k-means方法多支持向量机中k-means的目标是对训练数据进行划分,附加指导信息是保证k-means在对训练
在由多个计算机集群构成的多机群网格环境下，为了解决数据并行型计算（DPC）与计算资源的有效匹配问题，提出了一个基于强化学习机制的网格资源调度模型；给出了由多个计算机机群组成
数据调度问题是P2P流媒体研究中的核心问题。本文考虑Peer结点在带宽资源等方面的并构性，以分层编码为基础，提出了一种基于期望失真的数据包调度算法。它用期望失真来表示每个
社会保障因素会改变居民对未来的预期,从而对其资产配置决策有着重要的影响。在相关文献综述的基础上,以跨期的消费和投资资产组合理论为基础,将社会保障因素和预防性储蓄因
根据分布式测控网络系统实时通信的特点及实时性的内在要求，提出了实时服务质量的概念及指标体系，建立了抽象的实时服务质量数学函数，并用实时服务质量具体指标对实时消息进行约