::<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, finddefine thea bestmodified covergreedy algorithm, that doesselects notthe violateset <math>S_i</math> that has the budgetbest ratio of weighted uncovered elements to cost. Second, among covers of cardinality <math>1, 2, ..., k-1</math>, find the best cover that does not violate the budget. Call this cover <math>H_1</math>. NextThird, find all covers of cardinality <math>k</math> that do not violate the budget. Using these covers of cardinality <math>k</math> as starting points, apply the modified greedy algorithm, maintaining the best cover found so far. Call this cover <math>H_2</math>. At the end of the process, the approximate best cover will be either <math>H_1</math> or <math>H_2</math>. This algorithm achieves an approximation ratio of <math>1- {1/ \over e}</math> for values of <math>k \geq 3</math>. This 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]. ''Inf. Process. Lett''. 70, 1 (Apr. 1999), 39-45.</ref>
