Tight Approximation Bounds for Maximum Multi-Coverage
In the classic maximum coverage problem, we are given subsets T1,…,Tm 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∈STi∣. 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)=∑i∈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)=∑e∈[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−ℓ!ℓℓ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−2πℓ1. We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture.
