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

作者：崔鹏; 钱丽艳

来源：计算机科学, 2007, (10): 219-220+237.

• 集合多覆盖
• 宽度优先贪心算法
• 乘性权重更新方法 Set multicover
• Breadth first greedy algorithm
• Multiplicative weights update method

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

• 单位
  北京大学