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

作者：宫兴荣; 何尚录; 杨留猛

来源：四川兵工学报, 2012, (12): 126-128.

• 组合最优化
• 背包约束
• 下模集函数
• 贪婪算法

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

• 出版日期2012
• 单位兰州交通大学