The Greedy \(1-1/e\) Guarantee
11 min read
We have a budget of \(k\) choices and an objective with diminishing returns. The standard example is coverage: we pick \(k\) of \(d\) candidate sets to cover as many items as possible, and each set is worth less once its items are already covered by earlier picks. Checking all \(\binom{d}{k}\) subsets is hopeless once \(d\) runs into the thousands, so we do the obvious thing: start empty and, \(k\) times over, add whatever helps most right now. This is the greedy algorithm, and the question is how much its shortsightedness costs us.
The answer is a theorem: for any monotone submodular objective, greedy reaches at least a \(1 - 1/e \approx 0.63\) fraction of the best possible \(k\)-set, and no algorithm running in polynomial time can promise more. On any diminishing-returns problem, greedy is worth trying before anything cleverer. This theorem, due to Nemhauser, Wolsey & Fisher [NWF, ’78], is why.
Diminishing Returns
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.
Now the two properties. 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.
Monotone and submodular is the entire hypothesis. What we still owe is the algorithm those properties justify and the benchmark it is measured against.
The Greedy Algorithm
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. We will show that greedy clears a fixed fraction of it:
\[ f(S_k) \ge \Big(1 - \frac{1}{e}\Big) f(O^*), \]
and that fraction depends on nothing: not on \(f\), not on \(d\), not on \(k\).
The Gap Shrinks
The whole proof rests on one inequality: wherever greedy currently stands, some available element recovers a \(1/k\) share of the distance still left to \(f(O^*)\). The reason to expect it is a counting argument: the optimal set has \(k\) elements and between them they close the entire gap, so at least one of them closes a \(1/k\) share of it. 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). \]
In words: at every point in the run, some single element still on the table is worth at least a \(1/k\) share of the distance left to the optimum. Greedy takes exactly that element, 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). \]
Now track 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. \]
That factor is the same at every step, so applying it \(k\) times walks the gap back to the start:
\[ \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 starting gap is the whole optimum, \(\delta_0 = f(O^*) - f(\emptyset) = f(O^*)\), which is where the normalization \(f(\emptyset) = 0\) pays off. A calculus fact turns the \(k\)-th power into a constant. 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). Putting the unrolled recursion and this bound together:
\[ f(O^*) - f(S_k) = \delta_k \le \Big(1 - \frac{1}{k}\Big)^k f(O^*) \le \frac{1}{e}\,f(O^*), \]
and moving \(f(S_k)\) across leaves the guarantee we were after:
\[ f(S_k) \ge \Big(1 - \frac{1}{e}\Big) f(O^*). \]
Greedy never sees \(f(O^*)\) and never plans ahead, and taking the best available element each step still secures a fixed fraction of whatever gap remains. A fixed fraction secured every step is geometric decay, and over \(k\) steps that is the \((1 - 1/k)^k\). In the plot the thin vertical segments are the gaps \(\delta_i\) as a fraction of \(f(O^*)\), each shorter than the last by that factor, and the curve only clears the \(1 - 1/e\) line at the final step.
So shortsightedness costs at most a factor \(1/e\) of the optimum. Whether a sharper reading of the same algorithm would recover some of it is the next question.
The Constant Is Sharp
The argument spent an inequality at four separate points: monotonicity, submodularity, the bound by \(k\) times the largest gain, and the final \((1 - 1/k)^k \le 1/e\). A chain that long is usually loose somewhere. Stopping one line early, before the appeal to \(e\), leaves the exact fraction promised at a given budget:
\[ 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.
None of that slack comes from the proof being wasteful. Coverage instances land greedy exactly on the 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\).
The tie should bother you: greedy lands on the curve only because it is free to break a tie badly. But 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\).
The remaining \(1/e\) is not something a different algorithm can reclaim either. 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. That a shortsighted rule costing \(O(dk)\) evaluations is optimal among all efficient algorithms is why this bound turns up as often as it does.
Where It’s Used
The proof asks only for monotonicity and submodularity, so the guarantee 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.
Two practical notes before reaching for it. 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]). And \(1 - 1/e\) is a worst-case floor: on real objectives greedy usually lands much closer to optimal, and the theorem is what bounds how bad the bad case gets. When an objective has diminishing returns, the obvious algorithm is already provably within a constant of the best any efficient algorithm can promise, so the effort goes into checking that the objective really is monotone and submodular.