预算型最大覆盖问题的近似算法

doi:10.3969/j.issn.1000-1565.2008.01.004

河北大学学报(自然科学版) ›› 2008, Vol. 28 ›› Issue (1): 7-9,13.DOI: 10.3969/j.issn.1000-1565.2008.01.004

预算型最大覆盖问题的近似算法

张生,何尚录

兰州交通大学,数理与软件工程学院,甘肃,兰州,730070

出版日期:2008-01-25 发布日期:2008-01-25
基金资助:
国家自然科学基金，兰州交通大学校科研和教改项目

Approximate Algorithm for the Budgeted Maximum Coverage Problem

ZHANG Sheng,HE Shang-lu

Online:2008-01-25 Published:2008-01-25

摘要/Abstract

摘要： 研究了给定预算常数的最大覆盖问题,给出了求解此问题的改进贪婪算法,得到了性能保证为1-e-1的近似算法.

关键词: 覆盖问题, 贪婪算法, 下模集函数, 性能保证

中图分类号:

O221.7

张生,何尚录. 预算型最大覆盖问题的近似算法[J]. 河北大学学报(自然科学版), 2008, 28(1): 7-9,13.

ZHANG Sheng,HE Shang-lu. Approximate Algorithm for the Budgeted Maximum Coverage Problem[J]. Journal of Hebei University (Natural Science Edition), 2008, 28(1): 7-9,13.

预算型最大覆盖问题的近似算法

Approximate Algorithm for the Budgeted Maximum Coverage Problem

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价