%0 Journal Article
%T Multiplicative Weights Update Analysis of Set Multicover<br>集合多覆盖问题的乘性权重更新分析
%A CUI Peng
%A QIAN Li-Yan
%A <br>崔鹏
%A 钱丽艳
%J 计算机科学
%D 2007
%I 
%X 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 (In 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/2) 1 obtained by randomized rounding method.The design of this algorithm fits in the framework of multi- plicative weights update method,proposed by Arora etc.recently.
%K Set multicover
%K Breadth first greedy algorithm
%K Multiplicative weights update method<br>集合多覆盖
%K 宽度优先贪心算法
%K 乘性权重更新方法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=5AC1634C15D8EDB4&yid=A732AF04DDA03BB3&vid=339D79302DF62549&iid=F3090AE9B60B7ED1&sid=D5C73DEF4CF8FAF3&eid=1D67BE204FBF4800&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=7