Content deleted Content added
Remove university name. |
The lower bound is conditional. |
||
Line 29:
== Greedy algorithm ==
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>{{cite book | last=Hochbaum | first=Dorit S. | authorlink=Dorit S. Hochbaum | editor-first=Dorit S. | editor-last=Hochbaum | year=1997 | chapter=Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems | title=Approximation Algorithms for NP-Hard 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 unless <math>P = NP</math>.<ref>{{cite article | last = Feige | first = Uriel | authorlink = Uriel Feige | title = A Threshold of ln ''n'' for Approximating Set Cover | journal = Journal of the ACM | volume = 45 | number = 4 |date=July 1998 | issn = 0004-5411 | pages = 634–652 | doi = 10.1145/285055.285059 | publisher = Association for Computing Machinery | ___location = New York, NY, USA}}</ref>
== Known extensions ==
| |||