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

作     者：崔鹏 钱丽艳 CUI Peng;QIAN Li-Yan

作者机构：中国人民大学信息资源管理学院北京100872 北京大学信息学院北京100871 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2007年第34卷第10期

页      码：219-220,237页

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

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

学科分类：07[理学] 070104[070104] 0701[理学-数学类] 

核心收录：

D　O　I：10.3969/j.issn.1002-137X.2007.10.057

馆 藏 号：203125519...