Maximum coverage problem with group budget constraints

We study the maximum coverage problem with group budget constraints (MCG). The input consists of a ground set X, a collection (psi ) of subsets of X each of which is associated with a combinatorial structure such that for every set (S_jin psi ), a cost (c(S_j)) can be calculated based on the combinatorial structure associated with (S_j), a partition (G_1,G_2,ldots ,G_l) of (psi ), and budgets (B_1,B_2,ldots ,B_l), and B. A solution to the problem consists of a subset H of (psi ) such that (sum _{S_jin H} c(S_j) le B) and for each (i in {1,2,ldots ,l}), (sum _{S_j in Hcap G_i}c(S_j)le B_i). The objective is to maximize (|bigcup _{S_jin H}S_j|). In our work we use a new and improved analysis of the greedy algorithm to prove that it is a ((frac{alpha }{3+2alpha }))-approximation algorithm, where (alpha ) is the approximation ratio of a given oracle which takes as an input a subset (X^{new}subseteq X) and a group (G_i) and returns a set (S_jin G_i) which approximates the optimal solution for (max _{Din G_i}frac{|Dcap X^{new}|}{c(D)}). This analysis that is shown here to be tight for the greedy algorithm, improves by a factor larger than 2 the analysis of the best known approximation algorithm for MCG.