A brief review of the greedy algorithm for the Set-Cover problem.

Click for background material…

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:

Theorem ([3, 4, 1]).

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 $d$ th 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].

Bibliography

[1]	V. Chvátal. A greedy heuristic for the set-covering problem. Math. Operations Research, 4(3):233–235, 1979.
[2]	U. Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634–652, 1998.
[3]	D. S. Johnson. Approximation algorithms for combinatorial problems. J. Computer System Sciences, 9:256–278, 1974.
[4]	L. Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383–390, 1975.

Notes on algorithms

Lecture notes on algorithms

Set Cover / greedy algorithm

The algorithm

Performance guarantee

Related

Bibliography