期刊文献+

带权集合覆盖问题的一种随机近似算法 被引量:3

Randomized approximation algorithm for weighted set cover problem
下载PDF
导出
摘要 给出了集合覆盖问题的一种随机近似算法。给定E={e1,e2,…,en}的子集的集合S和S中每个子集的权值,带权的集合覆盖问题是从S中选择费用和最小的子集使得其并集覆盖E。对E中每一个未被覆盖的元素,以某一精心设计的概率分布选择包含该元素的子集,直到E中所有元素均被覆盖,算法结束。该算法求出的覆盖的费用的期望值不超过B.opt,其中opt为最优覆盖的费用,B=maxe∈E{|L(e)|},L(e)={s|e∈s,s∈S}。算法时间复杂度为O(n),其中n为E的元素数目。 A randomized approximation algorithm for the set cover problem was proposed. Given a collection S of subsets of E= {el ,e2……en} with weights on the subsets, the goal of the weighted set cover problem is to cover all the elements of E by picking a subset with the minimum total cost from S . For each uncovered element of the set E, a subset which contains the element was chosen with a certain elaborately designed probability distribution. The algorithm will not terminate until all the elements have been covered. The proposed algorithm computes a cover whose expected cost is at most B. opt where opt is the cost of some optimal cover for the problem, where B=max{|L(e)|} and eE E L(e)={s|e∈s,s∈S}. The running time of the algorithm is O(n) wheren is the cardinalityof E.
出处 《吉林大学学报(工学版)》 EI CAS CSCD 北大核心 2007年第2期429-432,共4页 Journal of Jilin University:Engineering and Technology Edition
基金 国家自然科学基金资助项目(60573024)
关键词 计算机应用 随机算法 近似算法 集合覆盖 computer application randomized algorithm approximation algorithm set cover
  • 相关文献

参考文献12

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

二级参考文献6

  • 1Corman T., Leiserson C., Rivest R., Stein C.. Introduction to Algorithms. MA: The MIT Press, 1990.
  • 2Vazitani V.. Approximation Algorithms. New York: Springer-Verlag, 2001.
  • 3Johnson D.S.. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 1974, 9(3): 256~278.
  • 4Feige U.. A threshold of lnn for approximating set cover. Journal of the ACM, 1998, 45(4): 634~652.
  • 5Hochbaum D.S.. Approximation Algorithm for NP-Hard Problems. Boston, MA: PWS Publishing Company, 1997.
  • 6Raz R., Safra S.. A sub-constant error-probability low-degree test and sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, El Paso, Texas, United States, 1997, 475~484.

共引文献3

同被引文献8

  • 1朱晓波,钱振东,陆振波,时幸飞.高速公路紧急救援服务点选址模型的研究[J].交通运输工程与信息学报,2010,8(4):104-109. 被引量:12
  • 2[1]Karp R M.Reducibility among Combinatorial Problems[C]//Karp R M.Complexity of Computer Computations.New York:Plenum press,1972:85-103.
  • 3[3]王晓东.算法设计与分析[M].第2版.北京:电子工业出版社,2005:303-314.
  • 4Richard L.Church,Ross A.Gerrard.The Multi‐level Location Set Covering Model[J].Geographical Analysis.2010(4)
  • 5Peng Zhang.A new approximation algorithm for the k -facility location problem[J].Theoretical Computer Science.2007(1)
  • 6C.S. ReVelle,H.A. Eiselt,M.S. Daskin.A bibliography for some fundamental problem categories in discrete location science[J].European Journal of Operational Research.2007(3)
  • 7王炜,刘茂.应急物流基站阶段性规划优化问题研究[J].物流技术,2009,28(1):63-64. 被引量:6
  • 8王守强.k-median问题反向贪心随机算法[J].计算机科学,2012,39(7):232-236. 被引量:2

引证文献3

二级引证文献2

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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