Content deleted Content added
Citation bot (talk | contribs) m Alter: isbn, journal, template type. Add: citeseerx, year, pages, volume, journal, title, doi, isbn, author pars. 1-3. Converted bare reference to cite template. Removed parameters. Formatted dashes. | You can use this bot yourself. Report bugs here. | User-activated. |
Fixed the phrasing regarding the hardness of approximation. |
||
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>
| |||