1
$\begingroup$

A solution to an instance of the Maximum Coverage problem with a budget of k subsets can be approximated with a greedy algorithm that, at each iteration, picks one of the subsets that adds the most additional coverage. This has been shown to lead to a worst case performance of $(1 - 1/e) \cdot \mathsf{OPT}$, where $\mathsf{OPT}$ is the optimal amount of coverage possible for the problem. See Section 2 of this lecture.

The quantity $(1 - 1/e)$ is the asymptotic lower bound of a function $f(i) = 1 - (1 - 1/i)^i$, where $i$ is the current iteration within the interval $[1, k]$. Therefore, on the $k$th and final iteration, we have an approximation factor of $1 - (1 - 1/k)^k \cdot \mathsf{OPT}$.

What I am wondering is where each part of the $1 - (1 - 1/k)^k$ is derived from.

Here is my current understanding: During every iteration, the greedy algorithm picks the subset that offers the most additional coverage, which means we are adding at least $1/k$ elements to our total coverage.

This leaves at most $1 - 1/k$ elements still uncovered. There are k iterations, so we can multiply this quantity by itself k times. This gives us the quantity $(1 - 1/k)^k.$ Okay.

So where does the first $1$ in the quantity $1 - (1 - 1/k)^k$ come from? If $1/k$ shows the minimum number of additional elements covered on any iteration, $(1 - 1/k)^k$ shows the remaining elements not covered after k iterations, then does that mean $1 - (1 - 1/k)^k$ represents the portion of elements that are covered by the end? Am I missing anything here?

$\endgroup$

1 Answer 1

1
$\begingroup$

You are almost correct but not precisely correct.

Your this statement is incorrect:

If $1/k$ shows the minimum number of additional elements covered on any iteration.

It should rather be:

"At least $1/k$ fraction of uncovered elements are covered in any iteration".

Let us prove this statement. At any stage of the algorithm, let $U' \subseteq U$ be the set of uncovered elements. Here $U$ is the initial set of elements. Let $S_1,S_2,\dotsc,S_k$ be the optimal solution. In other words, $S_1,S_2,\dotsc,S_k$ cover all elements from $U$. Suppose that after $t$ iterations, the algorithm has picked $p$ sets from $S_1,S_2,\dotsc,S_k$ for some $0 \leq p\leq t$. Without loss of genrality, suppose these sets are $S_1,\dotsc,S_p$. Note that $S_{p+1},\dotsc,S_{k}$ covers $U'$. Therefore, there exists a set in the collection that covers at least $1/(k-p)$ fraction of $|U'|$. Since $1/(k-p) \geq 1/k$, we have that at least $1/k$ fraction of uncovered elements are covered in any iteration. This completes the proof of the statement. Now, we will apply this statement.

Since the algorithm picks the set with maximum cardinality; the chosen set always contains $1/k$ fraction of uncovered elements. Therefore, after the first iteration, at least $(1/k) \cdot |U|$ elements are covered. Hence at most $(1-1/k) \cdot |U|$ elements remain uncovered. Let the actual number of uncovered elements be $n_1$.

Applying the statement again for the second iteration. At most $(1-1/k) \cdot n_1$ elements remain uncovered after the second iteration. Let $n_2$ be the actual number of uncovered elements. Then, $n_2 \leq (1-1/k)^2 \cdot |U|$ since $n_1 \leq (1-1/k) \cdot |U|$.

Using induction, you can prove that after $k$ iterations, $(1-1/k)^k \cdot |U|$ elements are uncovered. Therefore, the number of covered elements after $k$ iterations are at least $(1-(1-1/k)^k) \cdot |U|$.

$\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.