Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
Jtuckerfoltz (talk | contribs) m Correct typo can -> cannot |
||
| (2 intermediate revisions by 2 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 34:
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 ==
| |||