Maximum coverage problem: Difference between revisions

Revision as of 14:26, 2 November 2009

Revision as of 14:29, 2 November 2009

Line 49:

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

A greedy algorithm will no longer produce solutions with a performance guarantee. Namely, the worst case behavior of this algorithm might be very far from the optimal solution. The approximation algorithm is extended by the following way:. First, find a solution using greedy algorithm. In each iteration of the greedy algorithm the tentative solution adds the set which contains the maximum weight of uncovered elements divided by the cost of the set. Second, compare the solution gained by the first step to the best solution which uses a small number of sets. Third, return the best out of all examined solutions. This algorithm achieves an approximation ratio of <math>\frac{e}{e-1}</math>.

== Generalized maximum coverage ==