| 预算型最大覆盖问题的近似算法 |
| |
| 引用本文： | 张生,何尚录.预算型最大覆盖问题的近似算法[J].河北大学学报(自然科学版),2008,28(1):7-9. |
| |
| 作者姓名： | 张生 何尚录 |
| |
| 作者单位： | 兰州交通大学,数理与软件工程学院,甘肃,兰州,730070 |
| |
| 基金项目： | 国家自然科学基金
,
兰州交通大学校科研和教改项目 |
| |
| 摘 要： | 研究了给定预算常数的最大覆盖问题,给出了求解此问题的改进贪婪算法,得到了性能保证为1-e-1的近似算法.
|
| 关 键 词： | 覆盖问题 贪婪算法 下模集函数 性能保证 |
| 文章编号： | 1000-1565(2008)01-0007-03 |
| 修稿时间： | 2007年6月17日 |
Approximate Algorithm for the Budgeted Maximum Coverage Problem |
| |
| 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. |
| |
| Authors: | ZHANG Sheng HE Shang-lu |
| |
| Abstract: | Discuss the maximum coverage problem subject to a budgeted constant,presents an improved greedy algorithm which has(1-e-1)-performance guarantee for this problem. |
| |
| Keywords: | coverage problem greedy algorithm submodular set function performance guarantee |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《河北大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《河北大学学报(自然科学版)》下载免费的PDF全文 |
