求解多背包约束下下模集函数最大值的近似算法及其性能保证

• 作者: 何尚录 李小平 赵杏利 雷习军
• 来源期刊: 温州大学学报（自然科学版）
• 学科: 数学
• 关键词: 下模集函数 贪婪算法 性能保证 背包约束
• 年，卷（期）: 2010,（1）
• 所属期刊栏目: 数学研究
• 页码范围: 6-10
• 页数: 5页
• 分类号: O224
• 字数: 2291字
• 语种: 中文
• DOI: 10.3875/j.issn.1674-3563.2010.01.002

摘要

将部分穷举法与贪婪算法相结合,给出求解多背包约束下非减下模集函数最大值的近似算法.证明了该算法的性能保证是1-e-1,算法的时间复杂性为O(3n4).

作者信息

序号	姓名	单位	发文数	被引次数	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