1
$\begingroup$

The unweighted maximum coverage problem is defined as follows:

Instance: A set $E = \{e_1,...,e_n\}$ and $m$ subsets of $E$, $S = \{S_1,...,S_m\}$.

Objective: find a subset $S' \subseteq S$ such that $|S'| = k $ and the number of covered elements is maximized.

The problem is NP-hard, but a simple greedy algorithm (at each stage, choose a set which contains the largest number of uncovered elements) achieves an approximation ratio of $1-\frac{1}{e}$.

In the following post, there is an example of when the greedy algorithm fails.

Tight instance for unweighted maximum coverage problem?

I wish to prove that the approximation ration for the greedy algorithm is tight. That is, the greedy algorithm is not an $\alpha-$approximation ratio for any $\alpha > 1-\frac{1}{e}$.

I think that if I will find, for any $k$, (or for an ascending series of $k's$), an instance where the number of elements covered by greedy algorithm is $1-(1- \frac{1}{k})^k$ times the number of elements covered by the optimal solution, the tightness of the ratio will be proved.

Can someone give a clue for such instances?

I thought of an initial idea: let $E = \{ a_1 ,...a_n,b_1,...,b_n,...,k_1,...,k_n\}$, a set with $n\cdot k$ elements. Let $S$ include $k$ sets of $n$ elements each, $A = \{ a_1 ,...a_n\},...,K= \{k_1,...,k_n\}$. The optimal solution will select these $k$ sets and cover all the elements in $E$. Now I want to add $k$ sets to $S$, that will be the solution the greedy algorithm will find, and will cover $1-(1- \frac{1}{k})^k$ of the elements in $E$. The first such set, of size $n$: $S_1 = \{a_1,...a_\frac{n}{k},b_1,...b_\frac{n}{k},...,k_1,...k_\frac{n}{k} \}$ ($\frac{n}{k}$ elements from each of the first $k$ sets). The second such set, of size $n - \frac{n}{k}$: $S_2 = \{a_\frac{n}{k},...a_{\frac{n}{k}+ (n - \frac{n}{k})\cdot\frac{1}{k}},b_\frac{n}{k},...,b_{\frac{n}{k}+ (n - \frac{n}{k})\cdot\frac{1}{k}},...,k_\frac{n}{k},...,k_{\frac{n}{k}+ (n - \frac{n}{k})\cdot\frac{1}{k}} \}$ , (that is, $(n - \frac{n}{k})\cdot\frac{1}{k}$ elements from each of the first $k$ sets) and so on till we have $k$ additional such sets.

I don't think this idea works for every $k$ and $n$, and I'm not sure it's the right approach.

Thanks.

$\endgroup$
  • $\begingroup$ See Section 3.1 here for a weighted instance. You can get arbitrarily close to it using an unweighted instance by duplicating elements. $\endgroup$ – Yuval Filmus Nov 21 '19 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.