集合多覆盖问题的乘性权重更新分析

摘要：

集合多覆盖问题的简单贪心算法的近似比是lnn+1.本文提出简单贪心算法的一个变形,宽度优先贪心算法,并且证明其有近似比(ln n)/r+lnlnz+O(1),其中r是覆盖要求.这个结果比由随机取整方法得到的近似比O((lnn)/r+√(lnn/)r)+1为优.宽度优先贪心算法的设计可以归入Aora等最近提出的乘性权重更新方法的框架.

关键词：集合多覆盖、宽度优先贪心算法、乘性权重更新方法

所属期刊栏目：34

分类号：TP3(计算技术、计算机技术)

在线出版日期：2007-12-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：219-220,237