Maximum coverage problem: Difference between revisions

Revision as of 14:25, 2 November 2009

Revision as of 14:26, 2 November 2009

Line 41:

== Budgeted maximum coverage ==

In the budgeted maximum coverage version not only does every element <math> e_j </math> hashave 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.

:maximize <math>\sum_{e \in E} w(e_j) \cdot y_j </math>. (maximizing the weighted sum of covered elements).