Content deleted Content added
No edit summary |
Jtuckerfoltz (talk | contribs) m Correct typo can -> cannot |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 10:
: Instance: A number <math> k </math> and a collection of sets <math> S = \{S_1, S_2, \ldots, S_m\} </math>.
: Objective: Find a subset <math> S' \subseteq S</math> of sets, such that <math> \left| S' \right| \leq k</math> and the number of covered elements <math> \left| \bigcup_{S_i \in S'}{S_i} \right| </math> is maximized.
The maximum coverage problem is [[NP-hard]], and
This result essentially matches the approximation ratio achieved by the generic greedy algorithm used for [[Submodular set function#Optimization problems|maximization of submodular functions with a cardinality constraint]].<ref name="NVF">[[George Nemhauser|G. L. Nemhauser]], L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I, Mathematical Programming 14 (1978), 265–294</ref>
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. | author-link=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=978-053494968-6 | pages=94–143}}</ref> ln-approximability 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 journal | last = Feige | first = Uriel | author-link = 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| s2cid = 52827488 | doi-access = free }}</ref>
== Known extensions ==
The inapproximability results apply to all extensions of the maximum coverage problem since they hold the maximum coverage problem as a special case.
The Maximum Coverage Problem can be applied to road traffic situations; one such example is selecting which bus routes in a public transportation network should be installed with pothole detectors to maximise coverage, when only a limited number of sensors is available. This problem is a known extension of the Maximum Coverage Problem and was first explored in literature by
== Weighted version ==
| |||