The Greedy Algorithm for Submodular Maximization

In Part 1, I defined submodular functions and showed that they capture the pattern of diminishing returns across sensor placement, document summarization, influence maximization, and many other domains. I formalized the constrained maximization problem: given a monotone submodular function $f$ and a budget $k$ , find $\max_{S \subseteq \mathcal{V}} f(S)$ subject to $|S| \leq k$ . I also showed that this problem is NP-hard: enumerating all $\binom{n}{k}$ candidate subsets is intractable for any realistic problem size.

The question becomes: how do we find a good solution efficiently, given that finding the exact optimum is out of reach? The answer lies in approximation algorithms.

Approximation Algorithms

An $\alpha$ -approximation algorithm for a maximization problem runs in polynomial time and, for every instance of the problem, returns a solution whose value is at least $\alpha \cdot \text{OPT}$ . Here $\text{OPT}$ is the value of the optimal solution. The factor $\alpha \in (0, 1]$ is called the approximation ratio (or performance guarantee).

For instance, a $\frac{1}{2}$ -approximation algorithm for a maximization problem produces a solution worth at least half of the true optimum, on every instance. Note that this lower-bound guarantee holds for the worst-case, so the algorithm may perform significantly better on many practical instances.

I can think of at least three reasons to care about approximation algorithms. They offer:

Polynomial-time solutions to NP-hard problems. We cannot solve these problems exactly in polynomial time (unless P $=$ NP), but we can get provably close.
A rigorous metric for comparing heuristics. Instead of “this heuristic works well on my benchmark,” you get results like “this algorithm is within 63.2% of optimal on every possible input”. The guarantee does not depend on the dataset!
Implicit bounds on the optimum. When an $\alpha$ -approximation algorithm returns a solution of value $V$ , it also tells you that $\text{OPT} \leq V / \alpha$ . That bound is useful when computing the exact optimum is too expensive, which tends to be the case in practice.

For minimization problems, the convention flips: $\alpha \geq 1$ , and the algorithm’s output is at most $\alpha \cdot \text{OPT}$ . A $2$ -approximation for a minimization problem never exceeds twice the optimal cost.

The Greedy Algorithm

The greedy algorithm for monotone submodular maximization under a cardinality constraint is as simple and elegant as it can be, and left me in awe when I first learned it.

It is a single unconditional loop that, starting from an empty set ( $\varnothing$ ), repeatedly adds the element with the largest marginal gain to the current solution. Each iteration adds a single element to the solution set, without repetitions, for a total of $k$ iterations. Once an element $e^*$ is greedily picked, it is never removed. The algorithm is greedy because each step makes the locally optimal choice of the element with the largest marginal gain.

\boxed{ \begin{aligned} & \textbf{Greedy}(f, \mathcal{V}, k) \\ & \quad S_0 \leftarrow \varnothing \\ & \quad \textbf{for } j = 1 \textbf{ to } k\textbf{:} \\ & \quad \quad e^* \leftarrow \arg\max_{e \in \mathcal{V} \setminus S_{j-1}} f(e \mid S_{j-1}) \\ & \quad \quad S_j \leftarrow S_{j-1} \cup \{e^*\} \\ & \quad \textbf{return } S_k \end{aligned} }

That’s it, that’s the entire algorithm. No relaxation step, no rounding, no linear program. Fully deterministic too!

Runtime. At each of the $k$ iterations, the algorithm evaluates $f(e \mid S_{j-1})$ for every element $e \in \mathcal{V} \setminus S_{j-1}$ . Each marginal gain computation requires one call to the value oracle for $f$ , the black box from Part 1. The total cost is $\mathcal{O}(n \cdot k)$ oracle calls.

A Worked Example: Sensor Coverage

Consider 6 candidate sensor locations on a grid, labeled $\{1, 2, 3, 4, 5, 6\}$ , and a budget of $k = 3$ . Each sensor covers a circular region, and the submodular function $f(S)$ measures the total area covered by the union of all sensors in $S$ . The sensors have different ranges, so each one covers a different amount of area on its own.

In the map below, solid circles are placed sensors, and dashed arcs mark the new area each remaining sensor would still add. Hover over any sensor to see its current marginal gain. Run the algorithm one step at a time, then try placing the sensors yourself and see if you can beat it.

Greedy Algorithm Debugger

Step 1 of 3

Greedy will score all 6 sensors by the area each one covers, then place the best.

covered 0.0%6 oracle calls

Marginal gains

New area each would add. One oracle call per bar.

3next pick+10.5%

1+9.8%

5+9.0%

6+8.4%

4+7.7%

2+6.6%

Step 1. The algorithm computes the marginal gain $f(\{e\}) - f(\varnothing) = f(\{e\})$ for each candidate $e \in \{1, \dots, 6\}$ , since the current set is empty. Suppose sensor 3 covers the largest area individually. We set $S_1 = \{3\}$ .

Step 2. The algorithm recomputes the marginal gain of each remaining element with respect to the current solution $S_1 = \{3\}$ . Sensor 5, which covers a region that barely overlaps with sensor 3, has the highest additional area. We set $S_2 = \{3, 5\}$ .

Step 3. Same logic. Sensor 1 adds the most new area given that sensors 3 and 5 are already placed. We set $S_3 = \{3, 5, 1\}$ .

It’s crucial to notice that, at each step, the marginal gain of the selected sensor decreases. The first sensor might cover 120 $\text{m}^2$ on its own; the second adds 95 $\text{m}^2$ of new area; the third adds only 60 $\text{m}^2$ . That decline is submodularity at work: the same sensor would have contributed more if placed earlier, when less ground was already covered.

For a ground set this small, you can enumerate all $\binom{6}{3} = 20$ possible subsets and verify that the greedy solution is close to (or exactly equal to) the true optimum. On realistic instances with thousands of candidate locations, enumeration is of course impossible, but the greedy solution is still guaranteed to be within a precise factor of the optimum. In this case, this factor is guaranteed to be approximately $63.2\%$ , as I’ll show in a moment.

The Approximation Guarantee

The following result, due to Nemhauser, Wolsey, and Fisher (1978)¹, is arguably the most celebrated theorem in submodular optimization.

Theorem. Let $f : 2^{\mathcal{V}} \rightarrow \mathbb{R}_+$ be a monotone submodular function, and let $k$ be a positive integer. The Greedy algorithm returns a set $S_k$ satisfying:
$f(S_k) \geq \left(1 - \frac{1}{e}\right) \cdot f(S^*)$
where $S^* = \arg\max_{|S| \leq k} f(S)$ is the optimal solution and $e \approx 2.718$ is Euler’s number.

Since $1 - 1/e \approx 0.632$ , the greedy algorithm always returns a solution worth at least $63.2\%$ of the true optimum. The guarantee holds for every monotone submodular function and every cardinality constraint $k$ . No randomization, no special structure, no tuning.

Two additional facts make this result striking:

The bound is tight: there exist instances where the greedy algorithm achieves exactly a $(1 - 1/e)$ fraction of the optimum and no better.
The bound is optimal: Feige (1998)² proved that no polynomial-time algorithm can achieve an approximation ratio better than $(1 - 1/e)$ for this problem, unless P $=$ NP.

In other words, the greedy algorithm gives us the best possible approximation guarantee for monotone submodular maximization under a cardinality constraint. This however doesn’t mean that greedy is the fastest algorithm for this kind of problem. If you are interested in faster variants, Part 3 and Part 4 of this series cover two of them.

Greedy vs Random

Pick a submodular objective below, then run the race. Greedy picks the element with the highest marginal gain at each step. Random picks blindly. Both select k elements from a ground set of n. How close does each strategy get to the optimum?

Hire a team that covers the most distinct skills. Each candidate knows 2–5 skills; overlapping skills don't count twice.

Ground set n

Budget k

Why Does It Work? A Proof Sketch

The proof has three key steps. I will renounce the full formalism for the sake of emphasizing the geometric intuition behind it.

Step 1: Each Greedy Step Closes a Fraction of the Gap

Let $S_j$ be the greedy solution after $j$ steps, and let $S^*$ be the optimal solution with $|S^*| \leq k$ . Define the gap at step $j$ as:

\delta_j \coloneqq f(S^*) - f(S_j)

The gap measures how far the current greedy solution is from the optimum. At step $j+1$ , the greedy algorithm picks the element $e^*$ with the largest marginal gain $f(e^* \mid S_j)$ .

The optimal solution $S^*$ contains at most $k$ elements. By the monotonicity of $f$ , we know that $f(S^* \cup S_j) \geq f(S^*)$ , so the total marginal gain of adding all elements of $S^* \setminus S_j$ to $S_j$ is at least $f(S^*) - f(S_j) = \delta_j$ . By submodularity, the marginal gains of individual elements of $S^*$ (with respect to $S_j$ ) sum to at least this gap³:

\sum_{e \in S^* \setminus S_j} f(e \mid S_j) \geq f(S^*) - f(S_j) = \delta_j

Since $|S^*| \leq k$ , at least one element in $S^*$ has marginal gain at least $\delta_j / k$ . The greedy algorithm picks the best element overall, so:

f(e^* \mid S_j) \geq \frac{\delta_j}{k}

In words: each greedy step closes at least a $1/k$ fraction of the remaining gap.

Step 2: The Gap Shrinks Geometrically

The inequality above means that after step $j+1$ :

\delta_{j+1} = f(S^*) - f(S_{j+1}) \leq \delta_j - \frac{\delta_j}{k} = \delta_j \cdot \left(1 - \frac{1}{k}\right)

Apply this recursively from the initial gap $\delta_0 = f(S^*) - f(\varnothing)$ , assuming $f(\varnothing) = 0$ , which is standard for these problems:

\delta_k \leq f(S^*) \cdot \left(1 - \frac{1}{k}\right)^k

Step 3: Bounding the Geometric Compound

The expression $(1 - 1/k)^k$ is a well-known sequence from calculus. It is monotonically increasing and converges to $1/e \approx 0.368$ as $k \to \infty$ ⁴.

$k$	$(1 - 1/k)^k$
$1$	$0.000$
$2$	$0.250$
$5$	$0.328$
$10$	$0.349$
$50$	$0.364$
$100$	$0.366$
$\to \infty$	$1/e \approx 0.368$

Convergence of (1 − 1/k)^k

The sequence rises steeply for small k and levels off well before k = 10. The dashed line marks the limit 1/e ≈ 0.368. Hover or tap a point to inspect its value.

Since $(1 - 1/k)^k \leq 1/e$ for all $k \geq 1$ , we get:

\delta_k \leq \frac{f(S^*)}{e}

Rearranging:

f(S_k) = f(S^*) - \delta_k \geq f(S^*) - \frac{f(S^*)}{e} = \left(1 - \frac{1}{e}\right) \cdot f(S^*)

Each step closes at least a $1/k$ fraction of the gap; the gap compounds geometrically; and the geometric compound $(1 - 1/k)^k$ is bounded above by $1/e$ .

Greedy Approximation Staircase

Each step closes at least a 1/k fraction of the remaining gap. The teal bars show f(S_j) rising; the faded region above is the gap δ_j. Step through to watch the gap compound geometrically.

Budget k

5 / 5

f(S₅) = 0.6723δ₅ = 0.3277(1 − 1/e) = 0.6321

When Greedy Fails

The $(1 - 1/e)$ guarantee depends critically on monotonicity. When $f$ is non-monotone (i.e., adding elements can decrease $f$ ), the greedy algorithm can perform arbitrarily badly.

The thesis chapter I drew this material from contains a concrete counterexample. Consider a ground set $\mathcal{V} = \{1, 2, \dots, n\}$ and define the non-monotone submodular function:

f(S) = \begin{cases} |S| & \text{if } n \notin S \\ 2 & \text{otherwise} \end{cases}

Let $2 \leq k < n$ . At the first step, the greedy algorithm adds element $n$ , because its marginal gain is $f(\{n\}) - f(\varnothing) = 2$ , which is the largest among all singletons (every other element has a gain of $1$ ). Once $n$ is in the solution, it stays there; the algorithm only adds elements, never removes them. The consequence: no matter what the algorithm picks in the remaining $k-1$ steps, the function value is stuck at $2$ , because the presence of $n$ forces $f(S) = 2$ for any $S$ containing $n$ .

The optimal solution is to take any $k$ elements other than $n$ , yielding $f(S^*) = k$ . The greedy solution achieves $f(S_k) = 2$ . The approximation ratio is $2/k$ , which goes to $0$ as $k$ grows. The algorithm gets trapped by a locally attractive choice that is globally catastrophic.

This tells us that, for non-monotone submodular functions, standard greedy is the wrong tool. Randomized variants like the Random Greedy algorithm (Buchbinder et al. 2014)⁵ recover a constant approximation ratio of $1/e \approx 0.368$ by introducing randomness into the selection step, at the cost of a weaker guarantee.

The type of constraint also matters. With a cardinality constraint, the greedy algorithm achieves $(1 - 1/e)$ . With a single matroid constraint (a generalization of cardinality constraints), the same ratio holds, though the analysis that proves it is more involved⁶. With knapsack constraints, where each element has a cost and the total budget is limited, one needs different algorithms altogether, which I’ll let you explore autonomously.

Looking Ahead

The greedy algorithm requires $\mathcal{O}(n \cdot k)$ function evaluations. For moderate problem sizes, this is fine. For massive datasets ( $n$ in the millions, $k$ in the thousands), even $\mathcal{O}(n \cdot k)$ becomes prohibitive.

The next two parts of this series attack that cost from different angles. In Part 3, I will show how Lazy Greedy exploits the diminishing returns property itself to skip most recomputations, keeping the $(1 - 1/e)$ guarantee fully intact. In Part 4, I will introduce the Stochastic Greedy algorithm, which replaces the full scan over $\mathcal{V}$ at each step with a random subsample. The total cost drops from $\mathcal{O}(n \cdot k)$ to $\mathcal{O}(n \cdot \ln(1/\varepsilon))$ ; the factor of $k$ becomes a logarithmic term, at the price of a slightly weaker guarantee.

Key Takeaways

The greedy algorithm for monotone submodular maximization under a cardinality constraint is simple: at each step, pick the element with the largest marginal gain. Repeat $k$ times.
It achieves an approximation ratio of $(1 - 1/e) \approx 0.632$ , provably the best any efficient algorithm can achieve for this problem.
The proof relies on a geometric argument: each greedy step closes at least a $1/k$ fraction of the remaining gap to the optimum, and after $k$ steps the residual gap is at most $f(S^*)/e$ .
The greedy algorithm requires $\mathcal{O}(n \cdot k)$ function evaluations. For massive datasets, this becomes too expensive, motivating the faster variants in Part 3 and Part 4.
Monotonicity is critical: without it, greedy can achieve an approximation ratio as bad as $2/k$ , which is effectively useless for large $k$ .