摘要
为有效求得背包约束条件下不同问题的解,我们往往采取不同的方式,以获得其最优解。但更多情况下,我们无法找出其精确最优解,这时我们将选取不同的变量,通过有效的算法,以获得该问题的近似解。我们利用线性规划的知识,分析最大化非减下模集函数在背包约束下近似算法,得出该算法计算复杂性为O(n5),性能保证为1-e-1。
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）.
出处
《淮阴工学院学报》
CAS
2010年第3期15-18,共4页
Journal of Huaiyin Institute of Technology
关键词
下模集函数
近似算法
性能保证
最优解
submodular set function
approximation algorithm
performance guarantee
optimal solution
