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$.

Link: Max coverage on Wikipedia

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?

  • $\begingroup$ 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$. $\endgroup$ – Chandra Chekuri Dec 9 '17 at 19:41
  • $\begingroup$ @ChandraChekuri Thank you. Do you have any link to a proof or somewhere that mentions this? $\endgroup$ – Soheil Dec 10 '17 at 7:27
  • $\begingroup$ the standard proof of (1-1/e) for Max Coverage gives you the formula if you stare at it. $\endgroup$ – Chandra Chekuri Dec 10 '17 at 21:29
  • $\begingroup$ @ChandraChekuri I see, thanks. $\endgroup$ – Soheil Dec 11 '17 at 6:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.