Tight analysis for the ration of $1-\frac{1}{e}$ in the unweighted maximum coverage problem

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.

• See Section 3.1 here for a weighted instance. You can get arbitrarily close to it using an unweighted instance by duplicating elements. Commented Nov 21, 2019 at 10:12
• Your "objective" depends on a variable "k", but this variable is not part of the "instance"?
– Stef
Commented Feb 20, 2023 at 12:26

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.