Approximation Algorithm

1. (*) In the max coverage problem, we are given a collection S of sets Si, S2,.Sm over elements e1, e2,..., en, and asked to cover as many elements as possible with k sets. We learned a simple greedy algorithm that is 1-1/e-approximate. Recall that the greedy algorithm chooses a set that covers the maximum number of uncovered sets in each iteration