The [[greedy algorithm]] for maximum coverage chooses sets according to one rule: at each stage, choose a set which contains the largest number of uncovered elements. It can be shown that this algorithm achieves an approximation ratio of <math>1 - \frac{1}{e}</math>.<ref>{{citationcite book | last=Hochbaum | first=D.Dorit S. | authorlink=Dorit S. Hochbaum |year editor-first=1997|contribution=ApproximatingDorit coveringS. and| packingeditor-last=Hochbaum problems:| Setyear=1997 cover,| vertexchapter=Approximating cover, independent set,Covering and relatedPacking Problems problems| title=Approximation algorithmsAlgorithms for NP-hardHard Problems problems| publisher=PWS Publishing Company | ___location=Boston | isbn=053494968-1 | pages=94–143}}</ref> Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for maximum coverage.<ref>Feige, U., "A threshold of ln n for approximating set cover", J. ACM 45, 634-652.</ref>
Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation
algorithm for maximum coverage.<ref>Feige, U., "A threshold of ln n for approximating set cover", J. ACM 45, 634-652. </ref>
