<p>In the <em>maximum coverage</em> problem (also known as max k-cover) we are given a universe <span class="math-container">$U = \{e_1,\ldots, e_n\}$</span> of elements, a collection <span class="math-container">$F = \{S_1,\ldots, S_m\} \subseteq 2^U$</span> of sets over <span class="math-container">$U$</span>, and an integer parameter <span class="math-container">$k$</span>. The goal is to find <span class="math-container">$k$</span> sets <span class="math-container">$G \subseteq F, |G| = k$</span> such that the cardinality of <span class="math-container">$\bigcup_{S \in G} S$</span> is maximized (maximizing the number of elements taken). By the celebrated work of Feige [1], maximum coverage cannot be approximated to a better ratio than (roughly) <span class="math-container">$(1-1/e)$</span>. However, it seems that the lower bound of [1] uses values of k such that <span class="math-container">$k \ll m$</span>. Does the problem become easier if <span class="math-container">$m-k \leq k$</span>? e.g., what is the strongest lower bound when <span class="math-container">$k = 0.9 \cdot m$</span>? Or, what is the strongest lower bound as a function of <span class="math-container">$r = \frac{k}{m-k}$</span>?</p>
<p>Any answer or pointer would be highly appreciated.</p>
<p>[1] Feige, U. 1998. A Threshold of ln n for Approximating Set Cover. Journal of the ACM, Vol. 45, No. 4, July 1998.</p>

CC BY-SA 4.0
2024-04-11T18:40:02.597Z
If $k = 0.9m$ then a random selection of $k$ subsets will cover a $0.9$ fraction of the universe, and so will be a $0.9$ approximation.
Yuval Filmus
CC BY-SA 4.0
2024-04-12T03:32:23.947Z
This is true, but is there still some lower bound?
John
CC BY-SA 4.0
2024-04-13T15:00:55.537Z
Yuval's observation implies that there cannot be a lower bound (i.e. hardness result) better than $0.9 m$.  In other words, the answer to your question "*Does the problem become easier if $m-k \le k$?"* is 'yes'.   What kind of lower bound do you want?
Neal Young
CC BY-SA 4.0
2024-04-16T01:55:24.510Z
Max Coverage is APX-Hard when $k \ge cm$ for some fixed constant $c < 1$ via reductions from bounded degree instances of 3D Matching etc. By adding dummy sets with singleton elements it seems that one can show APX hardness even when $k \simeq (1-\delta)m$ but the hardness goes down with $\delta$.
Chandra Chekuri
<approximation-algorithms><approximation-hardness><set-cover><covering-problems>
Is the Maximum Coverage Problem Remains as Hard when Taking Most Sets?
John
# Is the Maximum Coverage Problem Remains as Hard when Taking Most Sets?

(Asked by: username_0 on 2024-04-11)

In the *maximum coverage* problem (also known as max k-cover) we are given a universe $U = \{e\_1,\ldots, e\_n\}$ of elements, a collection $F = \{S\_1,\ldots, S\_m\} \subseteq 2^U$ of sets over $U$, and an integer parameter $k$. The goal is to find $k$ sets $G \subseteq F, |G| = k$ such that the cardinality of $\bigcup\_{S \in G} S$ is maximized (maximizing the number of elements taken). By the celebrated work of Feige [1], maximum coverage cannot be approximated to a better ratio than (roughly) $(1-1/e)$. However, it seems that the lower bound of [1] uses values of k such that $k \ll m$. Does the problem become easier if $m-k \leq k$? e.g., what is the strongest lower bound when $k = 0.9 \cdot m$? Or, what is the strongest lower bound as a function of $r = \frac{k}{m-k}$?

Any answer or pointer would be highly appreciated.

[1] Feige, U. 1998. A Threshold of ln n for Approximating Set Cover. Journal of the ACM, Vol. 45, No. 4, July 1998.

**Tags:** approximation-algorithms, approximation-hardness, set-cover, covering-problems
> **Comments:**
> **username_1**: If $k = 0.9m$ then a random selection of $k$ subsets will cover a $0.9$ fraction of the universe, and so will be a $0.9$ approximation.  
> **username_0**: This is true, but is there still some lower bound?  
> **username_2**: Yuval's observation implies that there cannot be a lower bound (i.e. hardness result) better than $0.9 m$.  In other words, the answer to your question "*Does the problem become easier if $m-k \le k$?"* is 'yes'.   What kind of lower bound do you want?  
> **username_3**: Max Coverage is APX-Hard when $k \ge cm$ for some fixed constant $c < 1$ via reductions from bounded degree instances of 3D Matching etc. By adding dummy sets with singleton elements it seems that one can show APX hardness even when $k \simeq (1-\delta)m$ but the hardness goes down with $\delta$.  

---

## 0 answers

