多背包约束下下模集函数最大值问题的近似算法

Maximizing submodular set functions subject to multiple knapsac constraints

给出了在实数范围内求解多背包约束条件下下模集函数最大值问题的一种改进的近似算法,是MaximSviridenko所给出的整数范围内求解单背包约束下下模集函数最大值的扩展.该算法的时间复杂性为:O(kn4),其性能保证为1-e-1/D.

This paper presented an improved approximation algorithm which has performance guarantee of 1-e-1/D in the range of real numbers for the problem of maximizing submodular set function subject to multiple knapsacks constrains.This expended the question in the range of integers of Maxim Sviridenko.Also,this algorithm requires O（kn4） function value computations.