Tight Approximation Bounds for Maximum Multi-coverage

摘要

In the classic maximum coverage problem, we are given subsets T_1,..., T_m 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_i|. It is well-known that the greedy algorithm for this problem achieves an approximation ratio of (1 - e~(-1)) and there is a matching inapproximabil-ity 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 ) |T_i|, 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 ∈ T_i}|}, 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 - 1/2πℓ~(1/2). We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture. This problem is motivated by the question of finding a code that optimizes the list-decoding success probability for a given noisy channel. We show how the multi-coverage problem can be relevant in other contexts, such as combinatorial auctions.