Content deleted Content added
Bender2k14 (talk | contribs) →Budgeted maximum coverage: Improved punctuation |
|||
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>.{{fact|date=Nov 2009}}
== Generalized maximum coverage ==
| |||