求解单背包约束下下模函数半定松驰算法  

Semidefinite Relaxation Algorithm for Solving a Submodular Set Function with Single Knapsack Constraint

作　　者：权梓杨 何尚录[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,兰州730070

出　　处：《淮阴工学院学报》2013年第5期19-22,共4页Journal of Huaiyin Institute of Technology

摘　　要：为有效求得背包约束条件下下模函数的解,往往采取不同的方式,以获得最优解,但更多情况下无法找出其精确最优解。针对这个问题,选取两种不同的方法,先对所求解通过添加变量进行约束,再应用贪婪算法,以获得该问题的最优近似解;利用线性规划的知识,分析最大化非减下模集函数在单背包约束下的近似算法,得出当σ>0.19时,算法(III)的性能保证大于0.732,并且随着σ的增大而接近最优解,算法(III)中的参数θ对某种大规模情形将不起作用。In order to obtain the optimal valid solution of a submodular set function,a series of different approach were often applied.But more often,it is impossible to identify the exact optimal solution.Constraint addition to the function by more variables and the approximate greedy algorithm were applied sequentially to get optimal approximate solution for the problem.Linear programming was used to analyze the approximate algorithm for maximizing non-decreasing submodular set function with single knapsack constraint.When σ was bigger than 0.19,performance guarantee of algorithm（III） was more than 0.732,and the results got closer to the optimal solution with a greater σ.But the parameter σ in algorithm（III） did not work in a certain large scale situation.

关 键 词：背包问题 组合优化 半定松驰 近似算法 最优解 

分 类 号：O221.1[理学—运筹学与控制论]