# Tight Approximation Bounds for Maximum Multi-Coverage

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

## Key facts

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

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

- [Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences](https://mlsanity.com/paper/2604.05953/) (2026)
- [COMRECGC: Global Graph Counterfactual Explainer through Common Recourse](https://mlsanity.com/paper/2505.07081/) (2025)
- [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 classic maximum coverage problem, we are given subsets T1, dots, 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) := |cupi ∈ S Ti|. It is well-known that the greedy algorithm for this problem achieves an approximation ratio of (1-e-1) and there is a matching inapproximability result. We note that in the maximum coverage problem if an element e ∈ [n] is covered by several sets, it is still counted only once. By contrast, if we change the problem and count each element e as many times as it is covered, then we obtain a linear objective function, C(∞)(S) = sumi ∈ S |Ti|, which can be easily maximized under a cardinality constraint. We study the maximum ℓ-multi-coverage problem which naturally interpolates between these two extremes. In this problem, an element can be counted up to ℓ times but no more; hence, we consider maximizing the function C(ℓ)(S) = sume ∈ [n] minℓ, |i ∈ S : e ∈ Ti| , subject to the constraint |S| ≤ k. Note that the case of ℓ = 1 corresponds to the standard maximum coverage setting and ℓ = ∞ gives us a linear objective. We develop an efficient approximation algorithm that achieves an approximation ratio of 1 - fracℓℓe-ℓℓ! for the ℓ-multi-coverage problem. In particular, when ℓ = 2, this factor is 1-2e-2 ≈ 0.73 and as ℓ grows the approximation ratio behaves as 1 - frac1√2π ℓ. We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture.