文献检索-宁波市创意产业特色资源库

限定检索结果

集合多覆盖问题的乘性权重更新分析: 收藏
分享
引用; 《计算机科学》2007年第10期34卷 219-220,237页; 作者：崔鹏钱丽艳中国人民大学信息资源管理学院北京100872 北京大学信息学院北京100871; 集合多覆盖问题的简单贪心算法的近似比是lnn+1。本文提出简单贪心算法的一个变形,宽度优先贪心算法,并且证明其有近似比(ln n)/r+lnlnn+O(1),其中r是覆盖要求。这个结果比由随机取整方法得到的近似比O ((lnn)/r+((lnn)/r)^(1/2))+1为...; 集合多覆盖问题的简单贪心算法的近似比是lnn+1。本文提出简单贪心算法的一个变形,宽度优先贪心算法,并且证明其有近似比(ln n)/r+lnlnn+O(1),其中r是覆盖要求。这个结果比由随机取整方法得到的近似比O ((lnn)/r+((lnn)/r)^(1/2))+1为优。宽度优先贪心算法的设计可以归入Arora等最近提出的乘性权重更新方法的框架。; 来源：详细信息评论

限定检索结果