Maximum coverage problem: Difference between revisions

Revision as of 20:46, 9 July 2015

Revision as of 23:44, 20 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: 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.<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 | month date= July | year = 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 ==