# 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. – Yuval Filmus Nov 21 '19 at 10:12