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

求解非增次模集函数最大值问题的近似算法及其性能保证 被引量：4

An Approximation Algorithm and Its Performance Guarantee for Maximizing Non-increasing Submodular set Function
原文传递
导出
摘要 次模集函数的最值问题在组合优化问题中有广泛的应用,给出了求解非增次模集函数最大值问题的一种近似算法,并讨论了所给算法的性能保证. Maximizing or minimizing submodular set function has wide use in combinatorial optimization problem, in this paper, we presents an approximation algorithm for maximizing non-increasing submodular set function, and discusses its performance guarantee.
作者 郝自军 高岳林 何尚录
机构地区 北方民族大学信息与计算科学学院 兰州交通大学数理与软件工程学院
出处 《数学的实践与认识》 CSCD 北大核心 2008年第12期145-151,共7页 Mathematics in Practice and Theory
基金 北方民族大学科研项目(2007Y044)
关键词 组合优化问题 次模集函数 近似算法 性能保证 combinatorial optimization problem submodular set function approximation algorithm performance guarantee
分类号 O157 [理学—基础数学]
  • 相关文献

参考文献3

  • 1Fujishige S. Submodular Functions and Optimization[M]. North-Holland Press,1991.
  • 2ILev V P. An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function[J]. Discrete Applied Mathematics, 2001,114:131-146.
  • 3ILev V P, Linker N. Performance guarantee of a greedy algorithm for minimizing a supermodular set function on comatroid[J]. European Journal of Operational Research, 2006,171: 648-660.

同被引文献13

  • 1FUJISHIGE S. Submodular Functions and Optimization[M]. North-Holland Press, 1991.
  • 2ILEV V E An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function[J]. Discrete Applied Mathematics, 2001 (114): 131 - 146.
  • 3ILEV V P, LINKER N. Performance guarantee of a greedy algorithm for minimizing a supermodular set function on comatroid[J]. European Journal of Operational Research, 2006(171): 648-660.
  • 4M SVIRIDENDO A. 1.5282-approximation algorithm for metric uncapacitated facility location problem[C]//Proceeding of 9th Conference on Integer Progamming and Combinatorial Optimization, Cambridge, MA, USA, 2002:458.
  • 5FISHER M L, NEMHAUER G L,WOLSEY L A. An analysis of approximations for maximizing su-bmoudlar set ftmctions.II [J]. Mathematical Programming study, 1978, 8:73-87.
  • 6NARAYANAN H. Submodular Functions and Electrical Networks[M]. Vehicles:North Holland, 1997.
  • 7Fujishige S. Submodular Functions and Optimization[M]. Elsevier 2005.
  • 8ILev V P. An approximation guarantee of the greedy descent algorithm for minimizing a supermod- ular set function[J]. Discrete Applied Mathematics 2001,114(1-3):131-146.
  • 9ILev V P and Linker N. Performance guarantee of a greedy algorithm for minimizing a supermodular set function on comatroid[J]. European Journal of Operational Research 2006, 171(2): 648-660.
  • 10Fadaei S etc. Maximizing non-monotone submodular set functions subject to different constraints: Combined algorithms[J]. Operations Research Letters, 2011, 39(6): 447-451.

引证文献4

二级引证文献1

数学的实践与认识
2008年 第12期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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