A brief review of the greedy algorithm for the Set-Cover problem.
-
![\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=3.75in]{shared/graphics/set_cover}](https://algnotes.info/b/wp-content/uploads/2011/02/img-00014.png?x58380)
The Set-Cover problem: Given a collection S of finite sets from a universe U and a cost c_ s for each set s\in S, the problem is to choose a minimum-cost set cover — a collection C of sets in S such that each element e\in U is contained in at least one set in C. The cost of C is \sum _{s\in C} c_ s. The figure shows a Set Cover instance with universe \{ a,b,c,d,e\} and four sets. The two sets labeled “1” form a set cover of size 2, covering all five elements in the universe.
The algorithm
| input: collection S of sets over universe U, costs c: S\rightarrow {\mathbb R}_+ | |
| output: set cover C | |
| 1. | Let C \leftarrow \emptyset . |
| 2. | Repeat until C is a set cover: |
| 3. | Find a set s\in S maximizing the number of elements in s not yet covered by any set in C, divided by the cost c_ s. |
| 4. | Add s to C. |
| 5. | Return C. |
Performance guarantee
The following performance guarantee was proved in the 1970’s:
The greedy set-cover algorithm returns a set cover of cost at most {\rm H}(d)\, {\textsc{opt}}, where {\textsc{opt}} is the minimum cost of any set cover, d = \max _{s\in S} |s| is the maximum set size, and {\rm H}(d)\approx 0.58+\ln d is the dth Harmonic number.
The guarantee actually holds with respect to the optimum fractional set cover. The proof is typically given as a charging argument, or by a primal-dual argument (constructing a related dual solution to bound opt).
The logarithmic approximation guarantee is the best possible in the following sense: if P\ne NP, in the worst case, no polynomial-time algorithm guarantees a cover of cost o({\textsc{opt}}\log n), where n=|U| is the number of elements to be covered [2].
