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

摘要

为有效求得背包约束条件下下模函数的解,往往采取不同的方式,以获得最优解,但更多情况下无法找出其精确最优解.针对这个问题,选取两种不同的方法,先对所求解通过添加变量进行约束,再应用贪婪算法,以获得该问题的最优近似解;利用线性规划的知识,分析最大化非减下模集函数在单背包约束下的近似算法,得出当σ＞0.19时,算法(Ⅲ)的性能保证大于0.732,并且随着σ的增大而接近最优解,算法(Ⅲ)中的参数θ对某种大规模情形将不起作用.