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

• 作者: 何尚录 李小平 赵杏利 雷习军
• 来源期刊: 淮阴工学院学报
• 学科: 数学
• 关键词: 下模集函数 近似算法 性能保证 最优解
• 年，卷（期）: 2010,（3）
• 页码范围: 15-18
• 分类号: O224
• 字数: 2881字
• 语种: 中文
• DOI: 10.3969/j.issn.1009-7961.2010.03.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何尚录	兰州交通大学数理与软件工程学院	39	118	5.0	8.0
2	李小平	兰州交通大学数理与软件工程学院	39	147	7.0	10.0
3	赵杏利	兰州交通大学数理与软件工程学院	7	8	2.0	2.0
4	雷习军	兰州交通大学数理与软件工程学院	7	8	2.0	2.0