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

Multiplicative Weights Update Analysis of Set Multicover

作　　者：崔鹏[1] 钱丽艳[2] 

机构地区：[1]中国人民大学信息资源管理学院,北京100872 [2]北京大学信息学院,北京100871

出　　处：《计算机科学》2007年第10期219-220,237,共3页Computer Science

摘　　要：集合多覆盖问题的简单贪心算法的近似比是lnn+1。本文提出简单贪心算法的一个变形,宽度优先贪心算法,并且证明其有近似比(ln n)/r+lnlnn+O(1),其中r是覆盖要求。这个结果比由随机取整方法得到的近似比O ((lnn)/r+((lnn)/r)^(1/2))+1为优。宽度优先贪心算法的设计可以归入Arora等最近提出的乘性权重更新方法的框架。The simple greedy algorithm for set multicover has approximation ratio. This paper presents a variation of the simple greedy algorithm, Breadth First Greedy Algorithm, and proves its approximation ratio can be （ln n）/r＋ lnlnn＋O（1）, where r is the cover requirement. This result is better than the approximation ratio O（（ln n）/r ＋ √（lnn）/r） ＋ 1 obtained by randomized rounding method. The design of this algorithm fits in the framework of multiplicative weights update method, proposed by Arora etc. recently.

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

分 类 号：O153.1[理学—数学]