Tight Approximation Guarantees for Concave Coverage Problems

In the maximum coverage problem, we are given subsets T1, ldots, Tm of a universe [n] along with an integer k and the objective is to find a subset S subseteq [m] of size k that maximizes C(S) := Big|bigcupi ∈ S TiBig|. It is a classic result that the greedy algorithm for this problem achieves an optimal approximation ratio of 1-e-1. In this work we consider a generalization of this problem wherein an element a can contribute by an amount that depends on the number of times it is covered. Given a concave, nondecreasing function varphi, we define Cvarphi(S) := suma ∈ [n]wavarphi(|S|a), where |S|a = |i ∈ S : a ∈ Ti|. The standard maximum coverage problem corresponds to taking varphi(j) = minj,1. For any such varphi, we provide an efficient algorithm that achieves an approximation ratio equal to the Poisson concavity ratio of varphi, defined by αvarphi := min_x ∈ mathbbN^* fracmathbbE[varphi(Poi(x))]varphi(mathbbE[Poi(x)]). Complementing this approximation guarantee, we establish a matching NP-hardness result when varphi grows in a sublinear way. As special cases, we improve the result of [Barman et al., IPCO, 2020] about maximum multi-coverage, that was based on the unique games conjecture, and we recover the result of [Dudycz et al., IJCAI, 2020] on multi-winner approval-based voting for geometrically dominant rules. Our result goes beyond these special cases and we illustrate it with applications to distributed resource allocation problems, welfare maximization problems and approval-based voting for general rules.