Maximum coverage problem: Difference between revisions

Revision as of 20:20, 9 July 2015

Revision as of 20:21, 9 July 2015

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 | 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.<ref>{{cite article | last = Feige, U.,| first = Uriel | authorlink = Uriel Feige | title = "A thresholdThreshold of ln ''n'' for approximatingApproximating setSet cover",Cover J.| journal = Journal of the ACM | volume = 45, 634| number = 4 | month = July | year = 1998 | issn = 0004-6525411 | pages = 634–652 | doi = 10.1145/285055.285059 | publisher = Association for Computing Machinery | ___location = New York, NY, USA}}</ref>

== Known extensions ==

Line 82:

== References ==

* {{Cite book | last=Vazirani | first=Vijay V. | authorlink=Vijay Vazirani | title=Approximation Algorithms | year=2001 | publisher=Springer-Verlag | isbn=3-540-65367-8 | pages=}}

* {{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 | month = July | year = 1998 | issn = 0004-5411 | pages = 634–652 | doi = 10.1145/285055.285059 | publisher = Association for Computing Machinery | ___location = New York, NY, USA}}

== External links ==