The Greedy \(1-1/e\) Guarantee
10 min read
Suppose we can choose \(k\) sets from \(d\) candidates and want their union to cover as many items as possible. A set becomes less useful as earlier choices cover more of its items. These diminishing returns suggest a simple strategy: repeatedly choose the set that adds the most new coverage. The concern is whether a good choice now prevents a much better collection later.
Greedy guarantees at least about 63% of the best possible coverage [NWF, ’78]. The same guarantee holds for any nonnegative, monotone submodular objective: adding an item never hurts, and its benefit can only decrease as the chosen group grows. The proof bounds how much progress each choice makes:
Diminishing Returns
What does the objective have to satisfy for greedy to have any hope? Against an arbitrary objective greedy has no hope: if the objective pays nothing until exactly the right \(k\) elements are all in hand, every partial set looks the same and greedy is choosing blind. Submodularity rules that out, and together with monotonicity it is everything the proof will assume.
Fix a ground set \([d] = \{1, \dots, d\}\) and an objective \(f : 2^{[d]} \to \mathbb{R}_{\ge 0}\) with \(f(\emptyset) = 0\). That normalization costs nothing, since subtracting \(f(\emptyset)\) leaves every marginal gain unchanged, and it makes a fraction of the optimum mean what it says. In the coverage example each element \(e \in [d]\) names a set \(A_e\) of items, and \(f\) counts the items covered by the sets we have picked:
\[ f(S) = \Big| \bigcup_{e \in S} A_e \Big|. \]
The marginal gain of adding an element \(e\) to a set \(S\) is the extra value \(e\) brings on top of \(S\):
\[ \Delta(e \mid S) = f(S \cup \{e\}) - f(S). \]
For coverage, that is the number of items in \(A_e\) that \(S\) does not already cover.
The objective is monotone if no element ever hurts:
\[ \Delta(e \mid S) \ge 0 \qquad\text{for every}\qquad e \in [d], \; S \subseteq [d], \]
and submodular if an element helps less the more you already have:
\[ \Delta(e \mid S) \ge \Delta(e \mid T) \qquad\text{whenever}\qquad S \subseteq T. \]
Coverage has both. Adding a set can only cover more items, so the count never drops. And a set contributes just its fresh items, of which there are fewer once more is already covered, so its gain shrinks as the picked collection grows. That second property is diminishing returns written on sets: a new sensor is worth less once nearby sensors are up.
Submodularity has an equivalent form in terms of unions and intersections instead of single elements, sometimes the easier one to check:
\[ f(S) + f(T) \ge f(S \cup T) + f(S \cap T) \qquad\text{for all}\qquad S, T \subseteq [d]. \]
The proof below uses only the marginal form. The two say the same thing, and neither direction is immediate.
Claim: the marginal and union–intersection forms of submodularity are equivalent.
Proof
Order \(W = S \setminus T\) as \(w_1, \dots, w_r\). Adding these elements to \(S \cap T\) one at a time builds up to \(S\), and adding the same elements to \(T\) builds up to \(S \cup T\), so both differences telescope into marginal gains:
\[ f(S) - f(S \cap T) = \sum_{j=1}^{r} \Delta\big(w_j \mid (S \cap T) \cup \{w_1, \dots, w_{j-1}\}\big), \]
\[ f(S \cup T) - f(T) = \sum_{j=1}^{r} \Delta\big(w_j \mid T \cup \{w_1, \dots, w_{j-1}\}\big). \]
Since \(S \cap T \subseteq T\), each conditioning set on the first line is contained in its counterpart on the second, so the marginal form makes every term of the first sum at least the matching term of the second. Hence \(f(S) - f(S \cap T) \ge f(S \cup T) - f(T)\), which rearranges to the union–intersection form.
Conversely, take \(S \subseteq T\) and \(e \notin T\), and apply the union–intersection form to \(S \cup \{e\}\) and \(T\). These meet in \(S\) and join to \(T \cup \{e\}\), so
\[ f(S \cup \{e\}) + f(T) \ge f(T \cup \{e\}) + f(S), \]
and rearranging gives \(\Delta(e \mid S) \ge \Delta(e \mid T)\), the marginal form.
These two properties are all the guarantee needs: monotonicity lets us compare greedy’s set with the optimum joined onto it, and submodularity lets us price each optimal element at greedy’s current set instead of wherever it happens to land.
The Greedy Algorithm
What exactly does greedy do, and what do we compare it against? Greedy builds its set one element at a time. Start with \(S_0 = \emptyset\); having chosen \(S_i\), add the element of largest marginal gain:
\[ S_{i+1} = S_i \cup \{e_{i+1}\}, \qquad e_{i+1} = \operatorname*{argmax}_{e \notin S_i} \Delta(e \mid S_i), \]
and stop at \(S_k\), a set of size \(k\) (ties in the argmax break arbitrarily, and the guarantee holds however they fall). Each step scores at most \(d\) candidates and there are \(k\) steps, so the whole run costs \(O(dk)\) evaluations of \(f\), against \(\binom{d}{k}\) for brute force.
The benchmark is the best that any set of that size achieves. Write \(O^*\) for an optimal set, one maximizing \(f\) over all sets of size \(k\); there may be several, and any one will do.
Claim: for any monotone submodular \(f\) with \(f(\emptyset) = 0\) and any budget \(k\), greedy clears the following fraction of the optimum:
\[ f(S_k) \ge \Big(1 - \frac{1}{e}\Big) f(O^*). \]
The Gap Shrinks
Why does one greedy step recover a \(1/k\) share of what is still missing? Wherever greedy currently stands, some available element recovers a \(1/k\) share of the distance still left to \(f(O^*)\). The optimal set has \(k\) elements and together they close the entire gap, so at least one of them closes a \(1/k\) share. Submodularity is what turns that into a statement about the gain measured at greedy’s current set, rather than at whatever partial set the element happens to arrive on top of.
Fix the current set \(S\) and order the elements of \(O^*\) that greedy has not yet taken:
\[ O^* \setminus S = \{o_1, \dots, o_m\}. \]
Any order will do, and \(m \le k\) because \(O^*\) has \(k\) elements. Adding them to \(S\) one at a time gives the chain:
\[\begin{align} f(O^*) &\le f(S \cup O^*) \\ &= f(S) + \sum_{j=1}^{m} \Big[ f\big(S \cup \{o_1, \dots, o_j\}\big) - f\big(S \cup \{o_1, \dots, o_{j-1}\}\big) \Big] \\ &= f(S) + \sum_{j=1}^{m} \Delta\big(o_j \mid S \cup \{o_1, \dots, o_{j-1}\}\big) \\ &\le f(S) + \sum_{j=1}^{m} \Delta(o_j \mid S). \end{align}\]
The first line is monotonicity, since \(O^* \subseteq S \cup O^*\) and extra elements never lower \(f\). The second telescopes: consecutive brackets cancel in pairs, leaving \(f(S \cup \{o_1, \dots, o_m\}) = f(S \cup O^*)\) at one end and \(f(S)\) at the other. The third is the definition of the marginal gain. The fourth is submodularity, since each gain is measured on top of \(S\) together with the elements already added, and dropping those extras leaves the smaller set \(S\), where the gain can only be larger.
Subtracting \(f(S)\) from both ends turns the chain into a statement about the gap that is left:
\[ f(O^*) - f(S) \;\le\; \sum_{j=1}^{m} \Delta(o_j \mid S). \]
The sum has \(m \le k\) terms, and each one is at most the largest gain available anywhere at \(S\):
\[ f(O^*) - f(S) \;\le\; k \cdot \max_{e} \Delta(e \mid S). \]
Greedy takes an element attaining that maximum, so its step from \(S_i\) collects the whole maximum:
\[ f(S_{i+1}) - f(S_i) = \max_e \Delta(e \mid S_i) \;\ge\; \frac{1}{k}\big(f(O^*) - f(S_i)\big). \]
Define the gap left after \(i\) steps:
\[ \delta_i = f(O^*) - f(S_i). \]
The same constant \(f(O^*)\) sits in every \(\delta_i\), so it cancels in the difference and the drop in the gap is exactly the value greedy just gained:
\[ \delta_i - \delta_{i+1} = f(S_{i+1}) - f(S_i) \;\ge\; \frac{\delta_i}{k}. \]
Rearranging collects the step into a single factor:
\[ \delta_{i+1} \le \Big(1 - \frac{1}{k}\Big)\,\delta_i. \]
Applying the same factor for \(k\) steps bounds the final gap by the initial one:
\[ \delta_k \le \Big(1 - \frac{1}{k}\Big) \delta_{k-1} \le \Big(1 - \frac{1}{k}\Big)^{2} \delta_{k-2} \le \dots \le \Big(1 - \frac{1}{k}\Big)^{k} \delta_0. \]
The normalization \(f(\emptyset) = 0\) makes the starting gap \(\delta_0 = f(O^*)\). Concavity puts the logarithm below its tangent line at \(1\):
\[ \ln y \le y - 1 \qquad\text{for every}\qquad y > 0. \]
Take \(y = 1 - 1/k\), so the right side is \(-1/k\), and multiply through by \(k\):
\[\begin{align} k \ln\Big(1 - \frac{1}{k}\Big) &\le -1 \\ \Big(1 - \frac{1}{k}\Big)^{k} &\le e^{-1}, \end{align}\]
where the second line exponentiates the first (for \(k = 1\) the power is \(0\) and the bound holds outright). Combining the recursion with this bound gives:
\[ f(O^*) - f(S_k) = \delta_k \le \Big(1 - \frac{1}{k}\Big)^k f(O^*) \le \frac{1}{e}\,f(O^*), \]
and hence:
\[ f(S_k) \ge \Big(1 - \frac{1}{e}\Big) f(O^*). \]
In the plot, the normalized gaps \(\delta_i/f(O^*)\) decay geometrically, each bounded by the previous gap times \(1 - 1/k\).
The Constant Is Sharp
Could a sharper analysis, or a smarter algorithm, do better than \(1 - 1/e\)? The argument uses inequalities for monotonicity, submodularity, the bound by \(k\) times the largest gain, and the final comparison with \(1/e\). Before the comparison with \(1/e\), the recursion gives the exact fraction promised at budget \(k\):
\[ f(S_k) \ge \Big(1 - \Big(1 - \frac{1}{k}\Big)^k\Big) f(O^*). \]
At \(k = 1\) that fraction is \(1\), since a single pick takes the best element outright. As the budget grows it falls to \(1 - 1/e\), and never below.
Coverage instances attain this curve. Take \(k = 2\), where the guarantee reads \(3/4\), and three sets over the four items \(\{1, 2, 3, 4\}\):
\[ A_1 = \{1, 2\}, \qquad A_2 = \{3, 4\}, \qquad A_3 = \{1, 3\}. \]
The pair \(\{A_1, A_2\}\) covers everything, so \(f(O^*) = 4\). Every set has two items, so greedy’s first step is a three-way tie and it may take \(A_3\), the decoy that steals an item from each of the good sets. Whichever of \(A_1, A_2\) it adds next brings a single fresh item, for a total of \(3\). That is exactly \(\tfrac{3}{4} \cdot 4\), so the instance sits on the curve. The missed item is the price of never reconsidering \(A_3\).
Greedy lands on the curve only under an unfavorable tie, and every tight instance needs one. Equality in the guarantee forces equality at each step of the recursion, so the largest gain at \(S_i\) is exactly \(\delta_i / k\) and each of the \(k\) optimal elements offers exactly that much too. Greedy’s pick always ties with the optimal elements it passes over. Instances of this shape exist at every budget [NWF, ’78], so no sharper analysis of greedy can raise the constant at any \(k\).
Feige [Feige, JACM ’98] proved that beating \(1 - 1/e\) on coverage by any fixed constant is NP-hard, so no polynomial-time algorithm, greedy or otherwise, can guarantee more unless \(\mathrm{P} = \mathrm{NP}\). The \(O(dk)\) greedy rule is therefore optimal among efficient algorithms in its worst-case approximation factor.
Where It’s Used
Where else does the guarantee apply? The guarantee uses only monotonicity and submodularity, so it holds for any objective with diminishing returns, not just coverage. Placing \(k\) sensors to cut the most uncertainty about a signal, and choosing \(k\) experiments to learn the most about a parameter, both maximize a submodular information gain: a new sensor or experiment tells you less once similar ones are in place. Influence maximization, seeding \(k\) users so a message spreads farthest through a network, is monotone submodular as well, and that is how Kempe, Kleinberg & Tardos [KKT, KDD ’03] got the first guarantee for it. On this site, the data-selection page picks training points with an objective that is a sum of concave functions of modular scores. Such a sum is monotone submodular, so its greedy selection inherits exactly the \(1 - 1/e\) proved here.
Submodularity also makes greedy fast: because marginal gains only shrink as the set grows, a gain computed at an earlier step is an upper bound on its value now, so a lazy priority queue skips almost every re-evaluation (Minoux [Minoux, ’78]). The factor \(1 - 1/e\) is a worst-case floor; on real objectives greedy usually lands much closer to optimal.