求解多背包约束下下模集函数最大值的近似算法及其性能保证

Approximation Algorithm for Maximum of Submodular Set Function Subject to Multi-constraint Knapsack and Its Performance Guarantee

将部分穷举法与贪婪算法相结合,给出求解多背包约束下非减下模集函数最大值的近似算法.证明了该算法的性能保证是1–e–1,算法的时间复杂性为O(3n4).

A new approximation algorithm for maximum of a nondecreasing submodular set function subject to multi-constraint knapsack was given by combining partial exhaustive method with greedy algorithm. The performance guarantee of this algorithm is 1 - e^-1 and the time complexity of this algorithm is O（3n^4）.