Maximum coverage problem: Difference between revisions

Revision as of 16:37, 8 September 2015

Revision as of 16:38, 8 September 2015

Line 40:

:subject to <math> \sum{x_i} \leq k </math>; (no more than <math>k</math> sets are selected).

::<math> \sum_{e_j \in S_i} x_i \geq y_j </math>; (if <math>y_j \geq 0 </math> then at least one set <math>e_j \in S_i</math> is selected).

::<math>0y_j \leq y_jin \leq {0,1\}</math>; (if <math>y_j=1</math> then <math>e_j</math> is covered)

::<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 which 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 ==

In the budgeted maximum coverage version, not only does every element <math> e_j </math> have a weight <math>w(e_j)</math>, but also every set <math>S_i</math> has a cost <math>c(S_i)</math>. Instead of <math>k</math> that limits the number of sets in the cover a budget <math>B</math> is given. This budget <math>B</math> limits the weight of the cover that can be chosen.