The Greedy Algorithm and Its 63% Guarantee

Fix the central problem: given a monotone submodular function f over a ground set, choose at most k items to maximize f. This cardinality-constrained maximization is the workhorse case, covering sensor placement, summarization, and the rest.

It is NP-hard. The number of size-k subsets grows combinatorially, and there is no known way to search them efficiently for the exact best. Even the special case of maximum coverage, choosing k sets to cover the most elements, is NP-hard, so the general problem inherits the difficulty.

Exact optimization is therefore off the table for any real instance. The question becomes whether we can get provably close, and here the diminishing-returns structure delivers something remarkable: the crudest greedy strategy, which looks only one step ahead, comes with a worst-case guarantee that no efficient algorithm can beat.

The algorithm is the first thing anyone would try. Start with the empty set. Repeat k times: add the single item with the largest marginal gain given what you have chosen so far. Stop when you have k items.

S = {}
repeat k times:
    e* = argmax over e not in S of  [ f(S + e) - f(S) ]
    S = S + e*
return S

At each step it asks only one question: which single item helps most right now. It never reconsiders a past choice and never looks more than one item ahead. For sensor placement this means: place the sensor covering the most fresh river, then the next most, and so on.

It is obviously fast, requiring on the order of k passes over the items. What is not obvious, and is the heart of this lesson, is that this myopic procedure is nearly optimal.

In 1978 George Nemhauser, Laurence Wolsey, and Marshall Fisher proved the result that made this field, in their paper "An analysis of approximations for maximizing submodular set functions", in Mathematical Programming.

For any monotone submodular function with a cardinality constraint, the greedy algorithm returns a set whose value is at least a (1 - 1/e) fraction of the best possible. The number 1/e is about 0.37, so the guarantee is about 0.63: greedy always achieves at least 63% of the optimum, whatever the instance.

This is a worst-case bound, not an average. There is no input, however adversarial, on which greedy does worse than 63% of optimal for this problem. In practice it usually does far better, often within a percent or two of optimal, but the guaranteed floor is what makes it trustworthy: you can run a one-step-lookahead algorithm and know in advance it cannot embarrass you.

The intuition behind (1 - 1/e) is worth carrying, because it shows exactly where submodularity does the work.

At any step, the greedy pick is the best single item. Submodularity lets you argue that this best item captures a decent share of the gap still remaining to the optimum: because gains only diminish, the items the optimal solution would add cannot each be worth more later than the best item is worth now. So every greedy step closes at least a 1/k fraction of the remaining gap to optimal.

Closing a 1/k fraction of the gap k times leaves a factor of (1 - 1/k) to the power k of the gap unclosed. As k grows, that expression tends to 1/e. So the value achieved is at least (1 - 1/e) of optimal. The whole proof rests on the diminishing-returns inequality; remove submodularity and greedy has no guarantee at all.

A natural hope is that a cleverer polynomial-time algorithm could beat 63%. For this problem, it cannot, and that is a theorem, not a gap in our knowledge.

Uriel Feige proved in 1998, in a paper on approximating set cover, that maximum coverage cannot be approximated to better than (1 - 1/e) by any polynomial-time algorithm unless P equals NP. Since maximum coverage is a special case of monotone submodular maximization, the same limit binds the general problem.

So greedy is not merely good; it is optimal among efficient algorithms. The simplest thing you could write already achieves the best guarantee anyone can, short of a revolution in complexity theory. That coincidence, that the crudest strategy is also provably the best possible, is a large part of why submodular maximization is so satisfying and so widely used.

Plain greedy has one weakness at scale: each of the k rounds recomputes the marginal gain of every remaining item, which is expensive when items or the function are costly to evaluate.

Submodularity itself supplies the speed-up. Because marginal gains only decrease as the set grows, an item's gain computed earlier is an upper bound on its gain now. So keep the items in a priority queue ordered by their last computed gain. To pick the next item, pop the top, recompute only its gain, and if it is still at least the next item's stored value, it must be the true best, since every other gain can only have fallen. You select it without recomputing the rest.

This is the lazy greedy algorithm, first noted by Michel Minoux in 1978 and popularized as CELF by Jure Leskovec and colleagues in 2007. It returns exactly the same answer as greedy, often hundreds of times faster, and is what makes greedy practical on large data.

Return to the coverage example, choosing k equals 2 sets to cover the most elements:

A covers {1, 2, 3, 4}
B covers {3, 4, 5, 6}
C covers {5, 6, 7}

Round one, all gains are from empty: A gives 4, B gives 4, C gives 3. Greedy takes A, breaking the tie arbitrarily, covering {1,2,3,4}.

Round two, recompute gains given A. B adds 5 and 6, since 3 and 4 are covered: gain 2. C adds 5, 6, 7: gain 3. Greedy takes C, for a total coverage of {1,2,3,4,5,6,7}, all 7 elements.

Note what happened: B looked as good as A at the start, but its value collapsed once A was chosen, and C, initially the weakest, won round two. Greedy handled this correctly by always scoring against the current set. The optimal pair here is also A and C, so greedy was exactly optimal on this instance, as it very often is.

This lesson is the reason submodularity is worth knowing. A generic NP-hard selection problem, once shown to be monotone submodular, is solved by the simplest greedy rule to within a (1 - 1/e) factor of optimal, a bound that is provably the best any efficient algorithm can offer, and the lazy variant makes it fast enough for large instances.

That is a rare situation in combinatorial optimization: a hard problem where the easy algorithm is also the theoretically best one, with a guarantee you can quote before running it.

Everything so far has been the monotone case with a simple cardinality budget. The next lesson shows how much practical range that already covers, walking through sensor placement, influence maximization, and summarization as instances of exactly this template. The lesson after that handles what happens when the function is not monotone, or the constraint is more complex than a size limit.