::<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, findafter finding a solution using the greedy algorithm., Inreturn eachthe iterationbetter of the greedy algorithm, the tentative's solution addsand the set whichof contains the maximumlargest weight. ofCall uncoveredthis elementsthe divided byalgorithm the costmodified ofgreedy the setalgorithm. Second, comparestarting thewith solutionall gainedpossible byfamilies theof firstsets stepof sizes from one to the(at bestleast) solutionthree, whichaugment usesthese asolutions smallwith numberthe ofmodified setsgreedy algorithm. Third, return the best out of all examinedaugmented 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>
