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_j\in \psi $$ S j ∈ ψ , a cost $$c(S_j)$$ c ( S j ) can be calculated based on the combinatorial structure associated with $$S_j$$ S j , a partition $$G_1,G_2,\ldots ,G_l$$ G 1 , G 2 , … , G l of $$\psi $$ ψ , and budgets $$B_1,B_2,\ldots ,B_l$$ B 1 , B 2 , … , B l , and B. A solution to the problem consists of a subset H of $$\psi $$ ψ such that $$\sum _{S_j\in H} c(S_j) \le B$$ ∑ S j ∈ H c ( S j ) ≤ B and for each $$i \in {1,2,\ldots ,l}$$ i ∈ 1 , 2 , … , l , $$\sum _{S_j \in H\cap G_i}c(S_j)\le B_i$$ ∑ S j ∈ H ∩ G i c ( S j ) ≤ B i . The objective is to maximize $$|\bigcup _{S_j\in H}S_j|$$ | ⋃ S j ∈ 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+2\alpha })$$ ( α 3 + 2 α ) -approximation algorithm, where $$\alpha $$ α is the approximation ratio of a given oracle which takes as an input a subset $$X^{new}\subseteq X$$ X n e w ⊆ X and a group $$G_i$$ G i and returns a set $$S_j\in G_i$$ S j ∈ G i which approximates the optimal solution for $$\max _{D\in G_i}\frac{|D\cap X^{new}|}{c(D)}$$ max D ∈ G i | D ∩ X n e w | 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.