期刊文献+

奖励-收集顶点覆盖问题的精确算法

Exact algorithm for the prize-collecting vertex covering problem
下载PDF
导出
摘要 奖励-收集顶点覆盖问题是顶点覆盖问题的衍生问题,同时也是组合优化NP-hard问题。本文提出该问题的数学性质并给出证明,利用数学性质能够确定某些顶点一定在或一定不在最优奖励-收集顶点覆盖集中,从而降低该问题的规模;基于该问题的数学性质设计出上下界子算法、降阶子算法、回溯子算法,通过降阶子算法可以降低该问题的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间。通过应用和算法对比表明,所设计的算法比没有考虑该问题数学性质的一般精确算法的时间复杂度更低。 The prize-collecting vertex covering problem is not only a derivative of the vertex covering problem,but also a problem for NP-hard combinatorial optimization.In this paper,we firstly propose the mathematical properties of the problem and give the proof,which can determine that some vertices must or must not be in the optimal prize collection vertex covering set,so as to reduce the scale of the problem.Secondly,based on the mathematical properties of the problem,we design the upper and lower bound sub-algorithm,reduced-order sub-algorithm and backtracking sub-algorithm.Through the reduced-order sub-algorithm,the scale of the problem can be reduced,so as to shorten the search time of the backtracking sub-algorithm,and then reduce the time to solve the optimal solution of the problem.A comparison of applications and algorithms shows that the designed algorithm has lower time complexity than the general accurate algorithms without considering the mathematical properties of the problem.
作者 曾宾 宁爱兵 付振星 徐江盼 张惠珍 Zeng Bin;Ning Aibing;Fu Zhenxing;Xu Jiangpan;Zhang Huizhen(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)
出处 《计算机时代》 2023年第5期51-56,共6页 Computer Era
基金 国家自然科学基金(71401106) 上海市“管理科学与工程”高原学科建设项目。
关键词 奖励-收集顶点覆盖 上下界子算法 降阶子算法 回溯子算法 prize-collecting vertex cover upper and lower bound sub-algorithm reduced-order sub-algorithm backtracking subalgorithm
  • 相关文献

参考文献2

二级参考文献19

  • 1DINUR I, SAFRA S. The importance of being biased [ C ]//Proc of the 34th Annual ACM Symposium on Theory of Computing. New York : ACM Press, 2002 : 33-42.
  • 2MONIEN B, SPECKENMEYER E. Ramsey numbers and an approximation algorithm for the vertex cover problem[J]. Acta Informatica, 1985,22 ( 1 ) : 115-123.
  • 3CHLEBIKA M, CHLEBIKOVA J. Crown reductions for the minimum weighted vertex cover problem[J]. Discrete Applied Mathematics,2008,156(3): 292-312.
  • 4KHOTA S, REGEV O. Vertex cover might be hard to approximate to within 2-epsilon[ J]. Journal of Computer and System Sciences, 2008,74 ( 3 ) : 335-349.
  • 5KARAKOSTAS G. A better approximation ratio for the vertex cover problem [ J ]. ACM Trans on Algorithms,2009,5 (4) : 1 - 8.
  • 6NI Yao-dong. Stochastic minimum weight vertex cover problem[ C ]// Proc of the 5th International Conference on Information and Management Sciences. 2006 : 358-364.
  • 7ZADEH L A. Fuzzy sets [ J]. Information and Control, 1965,8 (3) : 338-353.
  • 8KAUFMANN A. Introduction to the theory of fuzzy subsets [ M ]. New York: Academic Press, 1975.
  • 9NAHMIAS S. Fuzzy variables [ J ]. Fuzzy Sets and Systems, 1978,1 (2) : 97-110.
  • 10LIU Bao-ding. Uncertainty theory: an introduction to its axiomatic foundations[ M ]. Berlin : Springer-Verlag, 2004.

共引文献2

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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