# Tight Approximation Guarantees for Concave Coverage Problems

arXiv: https://arxiv.org/abs/2010.00970 · HTML: https://mlsanity.com/paper/2010.00970/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2020.

## Built on by (most cited first, 4 of 4)

- [Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences](https://mlsanity.com/paper/2604.05953/) (2026)
- [Fine-Grained Complexity and Algorithms for the Schulze Voting Method](https://mlsanity.com/paper/2103.03959/) (2021)
- [Accelerated Relax-and-Round for Concave Coverage Problems](https://mlsanity.com/paper/2605.06900/) (2026)
- [Algorithms for Structured Elections under Thiele Voting Rules](https://mlsanity.com/paper/2607.28575/) (2026)

## Abstract (arXiv)

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.