IJPAM: Volume 41, No. 6 (2007)

IMPROVED GREEDY ALGORITHM FOR MAXIMUM
COVERAGE PROBLEM WITH GROUP
BUDGET CONSTRAINTS

Sheng Zhang$^1$, Xingquan Wang$^2$, Shanglu He$^3$
$^{1,2,3}$College of Mathematics, Physics and Software Engineering
Lanzhou Jiaotong University
Lanzhou, 730070, P.R. CHINA
$^1$e-mail: zs1005@126.com


Abstract.The main problem considered is maximum coverage problem with group budget constraints, which generalizes the budgeted maximum coverage problem. This problem is $NP$-hard and no exact approximation results are known for it. The contribution of this paper is a $(1-e^{-1})$-approximation algorithm for the maximum coverage problem with group budget constraint. We also show that this approximation factor is the best possible, unless $P=NP$.

Received: April 5, 2007

AMS Subject Classification: 90B99

Key Words and Phrases: coverage problem, greedy algorithm, group budget constraints

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2007
Volume: 41
Issue: 6