双背包约束下下模函数最大值的贪婪算法

A greedy algorithm for maximizing a submodular set function subject to double knapsack constraint

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

We proposed an approximation algorithm for maximizing a nondecreasing submodular set function subject to double knapsack constraint and proved the performance guarantee of this algorithm is 1-e-1. This algo- rithm is an improved greedy algorithm by combining partial enumeration method with the greedy algorithm. The time complexity of this algorithm is O（n4）.