求解背包约束下下模集函数近似算法及性能保证

为有效求得背包约束条件下不同问题的解,我们往往采取不同的方式,以获得其最优解。但更多情况下,我们无法找出其精确最优解,这时我们将选取不同的变量,通过有效的算法,以获得该问题的近似解。我们利用线性规划的知识,分析最大化非减下模集函数在背包约束下近似算法,得出该算法计算复杂性为O(n5),性能保证为1-e-1。

Solving Approximation Algorithm and Performance Guarantee of Submodular Set Function under Knapsack Constraint

To seek effective solutions for the different issues under knapsack constraint,we often adopt a different approach to obtain its optimal solution. But in most cases,we will select different variables by means of an effective algorithm to achieve similar solution for the problem when we can not find the exact maximum solutions. In the paper,linear programming knowledge is used to analyze the approximation algorithm for the maximization of non-decreasing submodular set function subject to a knapsack and obtain algorithm computing complexity-O（ n5） ,performance guarantee-（ 1-e-1）.