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

• 作者: 何尚录 权梓杨
• 来源期刊: 淮阴工学院学报
• 学科: 数学
• 关键词: 背包问题 组合优化 半定松驰 近似算法 最优解
• 年，卷（期）: 2013,（5）
• 所属期刊栏目: 数学
• 页码范围: 19-22
• 页数: 4页
• 分类号: O221.1
• 字数: 1874字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何尚录	兰州交通大学数理与软件工程学院	39	118	5.0	8.0
2	权梓杨	兰州交通大学数理与软件工程学院	1	1	1.0	1.0