【摘 要】
：
给出了集合覆盖问题的一种随机近似算法.给定E={e1,e2,,en）的子集的集合S和S中每个子集的权值,带权的集合覆盖问题是从S中选择费用和最小的子集使得其并集覆盖E.对E中每一个未
【基金项目】
：
国家自然科学基金资助项目（60573024）.
论文部分内容阅读
给出了集合覆盖问题的一种随机近似算法.给定E={e1,e2,,en）的子集的集合S和S中每个子集的权值,带权的集合覆盖问题是从S中选择费用和最小的子集使得其并集覆盖E.对E中每一个未被覆盖的元素,以某一精心设计的概率分布选择包含该元素的子集,直到E中所有元素均被覆盖,算法结束.该算法求出的覆盖的费用的期望值不超过B·opt,其中opt为最优覆盖的费用,B=max（e∈E）{｜ L（e）｜）,L（e）={S ｜e∈s,s∈S}.算法时间复杂度为O（n）,其中n为E的元素数目.
其他文献
根据步进运动原理,采用分立式布局,研制了大行程高分辨率精密旋转驱动器.该驱动器采用电磁杠杆柔性铰链箝位,以压电陶瓷为驱动源,采用柔性盘铰链把压电叠堆的直线运动转化成
本文力求从民族自治地方财政自治的基本内涵、客观基础、法律依据、现存问题及对策入手论述自己学习的体会,同时阐述了国外不同国家对财政自治的具体做法及其在中国的实践及
应用偏最小二乘法结合近红外光谱法（NIRS—PLS）对吡嗪酰胺片中吡嗪酰胺的含量进行了非破坏性定量分析。采用近红外一阶导数800—1200nm光谱区间建立了吡嗪酰胺片中吡嗪酰胺的含
目的:探讨石河子天山铝业公司高温作业环境对作业工人空腹血糖的影响。方法:610名高温作业工人为接触组,接触粉尘及其他有害因素工人643人为对照组,用迈瑞BS-400全自动生化分
在考虑了多径衰落信道的影响下改进了基于循环前缀的最大似然（ML）同步迭代算法，利用多个OFDM符号中相同位置的抽样点相加对参与相关计算的抽样点进行了修正，使抽样点的幅度变化降
猪喘气病属于农村散养型生猪的一种常见的传染性呼吸道疾病，对生猪的生长发育造成了严重影响。若发病后得不到有效控制将严重影响到生猪养殖户的切身利益。因此，本文主要介绍了
高等学校各门课程都具有育人功能，所有教师都负有育人职责。文章结合教学体会，就高职课程教学中贯穿德育教育的意义、原则和基本方法提出了自己的思考，供广大高职教师参考与实践
提出了一种新的快速多参考帧选择算法。用边缘检测及相关性信息确定候选参考帧集合,并利用P8×8模式下的运动矢量分布情况判断宏块的运动特性。该算法在JM10.2平台上进行
神话故事<四十个姑娘>对柯尔克孜的研究有特殊重要的意义,它的收集年代和版本、体裁等都是我们关注的重点.
本文认为,<民族素质论>的出版,既是对中国民族理论学科研究领域的拓展和深化,又是民族素质研究的标志性成果.它的学术贡献主要有:深度探讨了民族素质的概念;全面论述了研究民