Tight Approximation Guarantees for Concave Coverage Problems

This is the authors' abstract. We don't add key points for this paper.

In the maximum coverage problem, we are given subsets T₁, …, Tₘ of a universe $[n]$ along with an integer k and the objective is to find a subset S ⊆ [m] of size k that maximizes C(S) := |i ∈ S Tᵢ|. It is a classic result that the greedy algorithm for this problem achieves an optimal approximation ratio of 1-e⁻¹. 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 $φ$, we define C^φ(S) := ∑a ∈ [n]wₐφ(|S|ₐ), where |S|ₐ = | ∈ S : a ∈ Tᵢ\|. The standard maximum coverage problem corresponds to taking φ(j) = min,1\. For any such $φ$, we provide an efficient algorithm that achieves an approximation ratio equal to the Poisson concavity ratio of $φ$, defined by α_φ := minx ∈ N^* E[φ(Poi(x))]/φ(E[Poi(x)]). Complementing this approximation guarantee, we establish a matching NP-hardness result when $φ$ 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.