求解多维约束下下模函数最大值的改进贪婪算法  

AN IMPROVED GREEDY ALGORITHM FOR MAXIMIZING A SUBMODULAR SET FUNCTION WITH MULTIPLE CONSTRAINTS

作　　者：张生[1] 何尚录[2] 

机构地区：[1]内蒙古师范大学数学科学学院,呼和浩特010022 [2]兰州交通大学数理与软件工程学院,兰州730070

出　　处：《系统科学与数学》2009年第4期512-518,共7页Journal of Systems Science and Mathematical Sciences

基　　金：甘肃省自然科学基金(388685321)项目资助.

摘　　要：提出了多维约束下下模函数最大值问题,分析其在组合优化中的重要应用.此问题是NP-难的,故给出了求解该问题的改进贪婪算法.最后,从理论上证明了这一算法的时间复杂性和性能保证.说明该算法是多项式时间近似算法,同时也具有较好的性能保证.The problem of maximizing a submodular set function with multiple constraints is considered, which has important application in combinatorial optimization theory. The problem is NP-hard and then an improved greedy algorithm is given. The time complexity and performance analysis of the algorithm are proved, then it is shown that the algorithm is polynomial time approximate and has a relatively good performance.

关 键 词：组合优化 下模函数 贪婪算法 性能保证. 

分 类 号：O224[理学—运筹学与控制论]