期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

一种求解带权集合覆盖问题的近似算法

Approximation Algorithm for Weighted Set Cover Problem
在线阅读 下载PDF
导出
摘要 以优化形式描述的集合覆盖问题是一个NP难问题,设计快速有效的近似算法,具有重要的理论与现实意义.基于贪心算法思想,提出了一种求解带权集合覆盖问题的近似算法,并讨论了该算法的相对近似比. The set cover problem described with maximal form is an NP complex one. The authors paper proposed an approximative algorithm for weighted set cover problem, and then discussed the approximative ratio of the algorithm.
作者 张馨东 罗亮
机构地区 兰州交通大学
出处 《温州大学学报（自然科学版）》 2008年第6期46-48,共3页 Journal of Wenzhou University(Natural Science Edition)
关键词 带权集合覆盖 贪心算法 相对近似比 Weighted set cover problem Greedy algorithm Relative approximative ratio in this relative
分类号 O242.2 [理学—计算数学]
  • 相关文献

参考文献3

  • 1[1]Karp R M.Reducibility among Combinatorial Problems[C]//Karp R M.Complexity of Computer Computations.New York:Plenum press,1972:85-103.
  • 2[3]王晓东.算法设计与分析[M].第2版.北京:电子工业出版社,2005:303-314.
  • 3姚国辉,朱大铭,马绍汉,冯富宝.带权集合覆盖问题的一种随机近似算法[J].吉林大学学报（工学版）,2007,37(2):429-432. 被引量：3

二级参考文献12

  • 1张涌,朱洪.一类弱集合覆盖问题的近似算法[J].计算机学报,2005,28(9):1497-1500. 被引量：4
  • 2Karp R M.Reducibility among combinatorial problems[C]// Complexity of Computer Computations.New York:Plenum Press,1 972.
  • 3Johnson D S.Approximation algorithms for combinatorial probl6ms[J].J Comput System Sci,1974,9:256-278
  • 4Chvatal V.A greedy heuristic for the set-covering problem[J].Mathematics of Operations Research,1979,4:233-235.
  • 5Lovasz L.On the ratio of the optimal integral and fractional covers[J].Discrete Mathematics,1975,13:383-390.
  • 6Srinivasan A.Improved approximations of packing and covering problems[C]// Proc of 27th Annual ACM Symposium on the Theory of Computing,1995.
  • 7Slavik P.A tight analysis of the greedy algorithm for set cover[C]//Proc of 38th Annual ACM Symposium on Theory of Computing,1996.
  • 8Feige U.A threshold of Inn for approximating set cover[J].Journal of the ACM,1998,45(4):634-652.
  • 9Chuzhoy J,Naor J S.Covering problems with hard capacities[C]//The 43rd Annual IEEE Symoposium on Foundations of Computer Science.Vancouver,BC,Canada,2002.
  • 10Clarkson K L,Varadarajan K.Improved approximation algorithms for geometric set cover[c]//21st Annual Symposium on Computational Geometry.Pisa,Italy,2005.

共引文献2

温州大学学报（自然科学版）
2008年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部