Maximum coverage problem: Difference between revisions

Revision as of 13:42, 29 September 2015

Revision as of 01:25, 8 January 2016

Line 43:

::<math>x_i \in \{0,1\}</math> (if <math>x_i=1</math> then <math>S_i</math> is selected for the cover).

The greedy algorithm for the weighted maximum coverage at each stage chooses a set whichthat contains the maximum weight of uncovered elements. This algorithm achieves an approximation ratio of <math>1 - \frac{1}{e}</math>.<ref name="NVF"/>

== Budgeted maximum coverage ==