Editing Set cover problem (section)

== Greedy algorithm ==

There is a [[greedy algorithm]] for polynomial time approximation of set covering that chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements. This method can be implemented in time linear in the sum of sizes of the input sets, using a [[bucket queue]] to prioritize the sets.<ref>{{Introduction to Algorithms|edition=3|chapter=Exercise 35.3-3|pages=1122|mode=cs2}}</ref> It achieves an approximation ratio of <math>H(s)</math>, where <math>s</math> is the size of the set to be covered.<ref>{{citation
| last1=Chvatal | first1=V. | authorlink1=Václav Chvátal
| jstor=3689577
| title=A Greedy Heuristic for the Set-Covering Problem
| journal=[[Mathematics of Operations Research]]
| volume=4
| issue=3
| date=August 1979
| pages=233–235
| doi=10.1287/moor.4.3.233}}</ref> In other words, it finds a covering that may be <math>H(n)</math> times as large as the minimum one, where <math>H(n)</math> is the <math>n</math>-th [[harmonic number]]:
<math display=block> H(n) = \sum_{k=1}^{n} \frac{1}{k} \le \ln{n} +1</math>

This greedy algorithm actually achieves an approximation ratio of <math>H(s^\prime)</math> where <math>s^\prime</math> is the maximum cardinality set of <math>S</math>. For <math>\delta-</math>dense instances, however, there exists a <math>c \ln{m}</math>-approximation algorithm for every <math>c > 0</math>.<ref>
{{harvnb|Karpinski|Zelikovsky|1998}}</ref>

[[Image:SetCoverGreedy.gif|frame|Tight example for the [[greedy algorithm]] with k=3]]

There is a standard example on which the greedy algorithm achieves an approximation ratio of <math>\log_2(n)/2</math>.
The universe consists of <math>n=2^{(k+1)}-2</math> elements. The set system consists of <math>k</math> pairwise disjoint sets 
<math>S_1,\ldots,S_k</math> with sizes <math>2,4,8,\ldots,2^k</math> respectively, as well as two additional disjoint sets <math>T_0,T_1</math>,
each of which contains half of the elements from each <math>S_i</math>. On this input, the greedy algorithm takes the sets
<math>S_k,\ldots,S_1</math>, in that order, while the optimal solution consists only of <math>T_0</math> and <math>T_1</math>.
An example of such an input for <math>k=3</math> is pictured on the right.

Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover up to lower order terms
(see [[Set cover problem#Inapproximability results|Inapproximability results]] below), under plausible complexity assumptions. A tighter analysis for the greedy algorithm shows that the approximation ratio is exactly <math>\ln{n} - \ln{\ln{n}} + \Theta(1)</math>.<ref>Slavík Petr  [http://dl.acm.org/citation.cfm?id=237991 A tight analysis of the greedy algorithm for set cover]. STOC'96, Pages 435-441, {{doi|10.1145/237814.237991}}</ref>