# Approximating max coverage problem with slightly more than K sets

Definition of Max-Coverag

In the max-coverage problem, we are given $m$ subsets $\mathcal{S} = \{S_1, S_2, \ldots, S_m\}$ of a ground set $\{1, 2, \ldots, n\}$ and a number $K$. The goal is to choose a subset $\mathcal{S}'$ of $\mathcal{S}$ such that:

1. At most $K$ subsets in $\mathcal{S}$ are chosen, i.e., $|\mathcal{S}'| \leq K$,
2. The number of covered elements $|\bigcup_{S_i \in \mathcal{S'}} S_i|$ is maximized.

It is NP-hard to solve the problem exactly. But the greedy algorithm of iteratively choosing sets that contain the maximum number of "uncovered" elements gives a tight $1-1/e$ approximation. That is, no polynomial time algorithm can achieve a better than $1-1/e$ approximation unless $P = NP$.

My Question

The hardness results assumes that the algorithm chooses up to $K$ sets and show we cannot get a better than $1-1/e$ approximation. What if we allow the algorithm to choose a slightly more than $K$ sets? Can we get a better approximation factor?

• Greedy with $h$ sets will give a $1-(1-1/k)^h$-approximation. For $h=k$ you get at least $(1-1/e)$. The formula applies to both $h < k$ and $h \ge k$. – Chandra Chekuri Dec 9 '17 at 19:41
• @ChandraChekuri Thank you. Do you have any link to a proof or somewhere that mentions this? – Soheil Dec 10 '17 at 7:27
• the standard proof of (1-1/e) for Max Coverage gives you the formula if you stare at it. – Chandra Chekuri Dec 10 '17 at 21:29
• @ChandraChekuri I see, thanks. – Soheil Dec 11 '17 at 6:19