多维背包约束下单调非减下模函数最大值的贪婪算法  

作　　者：宫兴荣[1] 何尚录[1] 杨留猛[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,兰州730070

出　　处：《四川兵工学报》2012年第12期126-128,共3页Journal of Sichuan Ordnance

摘　　要：给出了求解多维背包约束下单调非减下模集函数最大值的近似算法,证明了该算法的性能保证是1-e-1。该算法结合了部分穷举法与贪婪算法,是对贪婪算法的一种改进,该算法的时间复杂性为O(n4)。

关 键 词：组合最优化 背包约束 下模集函数 贪婪算法 

分 类 号：TP221[自动化与计算机技术—检测技术与自动化装置]