Maximum coverage problem: Difference between revisions

Revision as of 02:43, 7 June 2011

Revision as of 18:55, 1 August 2011

Line 62:

:maximize <math>\sum_{e \in E, S_i} w_i(e_j) \cdot y_{ij} </math>. (maximizing the weighted sum of covered elements in the sets in which they are covered).

:subject to <math> \sum{c_i(e_j) \cdot w_y_{ij}} + \sum{c(S_i) \cdot x_i} \leq B </math>; (the cost of the selected sets cannot exceed <math>B</math>).

::<math> \sum_{i} y_{ij} \geqleq 1 </math>; (element <math>e_j=1</math> can only be covered by at most one set).

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

::<math>y_{ij} \in \{0,1\} </math>; (if <math>y_{ij}=1</math> then <math>e_j</math> is covered by set <math>S_i</math>)