【摘 要】
：
二分图受约束最小点覆盖问题作为一个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结点在带宽资源等方面的并构性，以分层编码为基础，提出了一种基于期望失真的数据包调度算法。它用期望失真来表示每个
介绍了一种新的提高湿敏元件耐水性和抗干扰特性的方法,即通过增涂衬底膜印保护膜,基本上解决了湿敏元件在高湿 环境中工作时,感湿膜易变形、起皱、与基片脱附的问题,从而在
设计和研制了红外接近觉传感器以探测物体的存在，设计和研制了机器人触须探测物体的触觉和模拟机械爪抓取物体的握力觉传感器。单片机系统控制传感器数据采集和初步判断，为机器
社会保障因素会改变居民对未来的预期,从而对其资产配置决策有着重要的影响。在相关文献综述的基础上,以跨期的消费和投资资产组合理论为基础,将社会保障因素和预防性储蓄因
根据分布式测控网络系统实时通信的特点及实时性的内在要求，提出了实时服务质量的概念及指标体系，建立了抽象的实时服务质量数学函数，并用实时服务质量具体指标对实时消息进行约