Content deleted Content added
Bender2k14 (talk | contribs) Added an intext citation. |
Bender2k14 (talk | contribs) →Budgeted maximum coverage: Added info about how this approximation ratio is proabably the best |
||
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>. The is the best possible approximation ratio unless <math>NP \subseteq DTIME(n^{O(\log\log n)})</math>.<ref>Khuller, S., Moss, A., and Naor, J. 1999. [http://dx.doi.org/10.1016/S0020-0190(99)00031-9 The budgeted maximum coverage problem]. <i>Inf. Process. Lett</i>. 70, 1 (Apr. 1999), 39-45.</ref>
== Generalized maximum coverage ==
| |||