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

Approximate Algorithm for the Budgeted Maximum Coverage Problem

作　　者：张生[1] 何尚录[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,甘肃兰州730070

出　　处：《河北大学学报（自然科学版）》2008年第1期7-9,13,共4页Journal of Hebei University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(604730304);兰州交通大学"青蓝"工程资助项目(QL-03-19A)

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

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

分 类 号：O221.7[理学—运筹学与控制论]