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$
2
  • $\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$ Nov 21, 2019 at 10:12
  • $\begingroup$ Your "objective" depends on a variable "k", but this variable is not part of the "instance"? $\endgroup$
    – Stef
    Feb 20, 2023 at 12:26

1 Answer 1

0
$\begingroup$

Your approach is mostly correct. The coverage of $S_i$ is $n ( 1 - 1 /k)^{i-1}$ and the sets $S_1, \ldots, S_k$ are disjoint, so the total coverage is $$ \sum_{i=1}^{k} n (1 - 1 / k)^{i-1} = n \left( \frac{1 - (1 - 1/k)^k}{1 - (1-1/k)} \right) = kn \left( 1 - (1 - 1/k)^k \right) = \mathrm{OPT} \cdot \left( 1 - (1 - 1/k)^k \right) $$ as required, where OPT is the optimal value ($nk = |E|$ in this case). The above sum is a simple Geometric series.

There are two small problems. Firstly, the sizes of the $S_i$s may not be integral. You can fix this by setting $n=k^{k-1}$ so that $$ |S_i| = k^{k-1} \left( \frac{k - 1}{k} \right)^{i-1} = k^{k-i}(k-1). $$

The second problem is that the algorithm will not necessarily select set $S_1$ over all of $A, B, \ldots, K$ as they are all provide $n$ additional coverage. You will have the same problem with all subsequent sets. You could reasonably just declare that the $S_i$s appear before $A, \ldots, K$ in the collection of sets, and that this is how the greedy algorithm tie-breaks. To be more thorough, you could add $k$ new elements to $E$, and add a unique new element to each of $S_1, \ldots, S_k$. The greedy algorithm is now obliged to choose $S_1, \ldots, S_k$ and achieves a coverage of $$ kn \left(1 - (1 - 1/k)^k) \right) + k = kn \left( 1 - (1 - 1/k)^k + 1 / k^{k-1} \right). $$ The new term $1 / k^{k-1}$ obviously goes to zero and the $1-1/e$ upper bound on the approximation factor is still proved.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.