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

张生; 何尚录

doi:10.3969/j.issn.1000-1565.2008.01.004

河北大学学报(自然科学版) >

2008 , Vol. 28 >Issue 1: 7 - 9,13

DOI: https://doi.org/10.3969/j.issn.1000-1565.2008.01.004

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

张生 ,
何尚录

展开

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

网络出版日期: 2008-01-25

基金资助

国家自然科学基金，兰州交通大学校科研和教改项目

收起

Approximate Algorithm for the Budgeted Maximum Coverage Problem

ZHANG Sheng ,
HE Shang-lu

Expand

Online published: 2008-01-25

Fold

摘要

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

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

本文引用格式

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

参考文献

[1] Berman O., Larson RC., Bertsimas D.. LOCATING DISCRETIONARY SERVICE FACILITIES.2. MAXIMIZING MARKET SIZE, MINIMIZING INCONVENIENCE [J]. Operations Research: The Journal of the Operations Research Society of America 1995, 4(4).
[2] BERMAN O, FOUSKA N, LARSON R C. Optimal location of discretionary service facilities [J]. Transportation Science 1992, 26(03).
[3] DORIT S, HOCHBAUM A. Approximation Algorithms for NP-hard problems [M]. Boston:PWS Publishing Company 1996.
[4] FUJISHIGE S. Submodular functions and optimization [M]. Amsterdam:Elsevier Science 2005.
[5] MAXIM S. A note on maximizing a submodular set function subject to knapsack constraint [J]. Operations Research Letters 2004, 32(05).
[6] CHANDRA C, AMIT K. Maximum coverage problem with group budget constraints and applications [J]. Lecture Notes in Computer Science 2004, 12(02).
[7] Samir Khuller, Anna Moss, Joseph (Seffi) Naor. The budgeted maximum coverage problem [J]. Information processing letters 1999, 1(1).

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

参考文献