The Exchange Argument: Proving a Greedy Choice Is Safe

A greedy algorithm commits to one locally attractive choice at a time and never reconsiders. The commitment is what makes it fast, and it is also what makes it suspicious. Nothing in the definition of “locally attractive” guarantees global optimality, and in general it does not hold. With coins of denominations 1, 3 and 4, making change for 6 by always taking the largest coin that fits yields 4 + 1 + 1, three coins, while 3 + 3 uses two. The greedy rule was followed exactly and the result was wrong by a factor of 1.5.

Correctness therefore has to be proved, not assumed, and the standard proof for a greedy algorithm is the exchange argument. It is a small piece of reasoning with a rigid shape, and learning to write it down precisely is most of the work of designing greedy algorithms.

What a correctness proof must establish

Two claims together imply that the greedy algorithm returns an optimal solution.

The first is the greedy choice property: there exists an optimal solution that contains the choice the algorithm makes first. This is a statement about existence, not about uniqueness. The optimal solution that agrees with the greedy first step may be different from the one you had in mind, and that is fine.

The second is optimal substructure: after the first choice is fixed, the remaining subproblem has the same form as the original, and an optimal solution to the original consists of the greedy choice plus an optimal solution to the remainder. For many greedy algorithms this is immediate because the remainder is literally the same problem on the leftover input; for others it needs an argument that removing the chosen element does not change the structure of what is left.

Induction on the number of choices then gives the result: the first choice is safe, the remainder is a smaller instance of the same problem, so the greedy solution is optimal by induction on instance size. Both claims must be checked; algorithms that satisfy one but not the other exist, and they fail.

The mechanics of an exchange

The greedy choice property is almost always proved by transforming an optimal solution rather than by constructing one. Let $G$ be the sequence of choices the greedy algorithm makes, $g_1, g_2, \dots, g_k$, and let $O$ be an optimal solution. Compare them position by position. If they are identical, there is nothing to prove. Otherwise let $i$ be the first index at which they differ, so $g_1 = o_1, \dots, g_{i-1} = o_{i-1}$ and $g_i \neq o_i$.

The exchange step constructs a second optimal solution $O’$ that agrees with $G$ on the first $i$ positions. It does so by removing $o_i$ from $O$ and inserting $g_i$, then repairing whatever the removal broke. Three obligations attach to the repair:

1. Feasibility. $O’$ must be a valid solution. If $O$ was a set of intervals, $O’$ must still contain no overlaps; if it was a spanning tree, $O’$ must still be connected and acyclic.
2. Cost. $O’$ must be no worse than $O$. Since $O$ is optimal, “no worse” means equal cost, and that equality is what carries the induction.
3. Containment. $O’$ must contain $g_i$, and it must still contain $g_1, \dots, g_{i-1}$.

If all three hold, $O’$ is an optimal solution whose first $i$ choices match the greedy algorithm. Repeating the argument at the next divergence produces an optimal solution matching the greedy prefix at every position, which is to say the greedy solution itself is optimal. The repetition is finite because each exchange strictly increases the length of the matching prefix, and the solutions are finite objects.

The proof obligation is therefore concentrated in one place: find the repair. When the repair exists and preserves cost, the algorithm is correct. When no repair exists, the algorithm may still be correct but this proof will not show it, and more often the algorithm is simply wrong.

A worked exchange: evicting the page needed furthest in the future

Belady’s rule for offline page replacement is a clean instance. A cache holds $k$ pages; a request sequence is known in advance; a fault forces one cached page to be evicted. The rule: evict the page whose next request is furthest away, treating a page never requested again as infinitely far.

Suppose an optimal policy $O$ and the greedy policy differ at the first fault, where greedy evicts page $x$ and $O$ evicts page $y$. Because greedy chose $x$, the next request for $x$ is no earlier than the next request for $y$; that is the only fact the proof needs. Construct $O’$ that behaves exactly like $O$ up to this fault, then evicts $x$ instead of $y$. After the fault, $O’$ holds $x$ where $O$ holds $y$, and the two caches are otherwise identical.

Until the next request for $y$, no request can distinguish the two caches, because $x$ is not requested in that interval by the choice of $x$. When $y$ is finally requested, $O$ may fault to load it while $O’$ already has it; from that point $O’$ can follow $O$‘s subsequent decisions, holding every page $O$ holds plus possibly $y$ instead of whatever $O$ loaded. Faults incurred by $O’$ up to that moment are no more than those incurred by $O$, and after it $O’$ never faults more often. So $O’$ is optimal and agrees with greedy at the divergence.

The subtle part is the phrase “by the choice of $x$”. If $x$ were requested before $y$, the swap would hand $O’$ a fault that $O$ avoided, and the cost argument collapses. The ordering of next-use times is exactly the repair that makes the exchange feasible at equal cost. A page never requested again has next-use time infinity, which is why evicting it is always the furthest-away choice when one exists.

Where the exchange fails, and what failure looks like

The coin example fails at the repair. Take the instance above: greedy picks 4, an optimal solution uses 3 + 3. To exchange, remove one 3 from the optimal solution and insert 4. Feasibility breaks immediately: the remaining 3 plus 4 exceeds 6. There is no repair, and indeed the greedy answer is not optimal. The greedy choice property is false for that coin system, and it is true for the canonical system 1, 2, 5, 10, 20, 50, 100 only because of a numerical property of those denominations, not because greedy is generally sound for change-making.

0/1 knapsack fails the same way. Ordering items by value-to-weight ratio and taking each one that fits looks like the fractional problem’s rule, and the fractional problem is solved optimally by exactly that rule. But in the integral problem the swap can violate the capacity constraint, and no repair preserves value: the greedy packing can be close to half the optimum when one dense item displaces two slightly less dense ones, and that factor of two is the worst case the rule can reach. The analysis of that gap is the subject of fractional relaxation and the knapsack gap.

For problems whose feasible sets are closed under taking subsets, there is a structural characterization of when a weight-ordered greedy rule has the exchange-always-succeeds property: the feasible sets must form a matroid. Spanning trees satisfy the criterion and 0/1 knapsack violates it. Interval scheduling is the useful counterexample to any converse: its earliest-finish rule is optimal for every instance, yet the family of pairwise disjoint intervals is not a matroid and the weight-ordered rule is not even the right form. The criterion is therefore sufficient for the standard greedy shape, not necessary for greedy correctness in general, and matroid greedy optimality develops it alongside that case. When the structure is not a matroid and the exchange fails, the natural next move is to quantify how much the repair can cost, which turns a failed correctness proof into an approximation guarantee, as described in approximation ratios and hardness.

Stays-ahead: the same argument in inductive clothing

Many proofs are written in a form called “greedy stays ahead”, which compares the greedy solution to an optimal one step by step instead of performing an explicit swap. After $i$ steps, one shows that the greedy partial solution is at least as good as the optimal partial solution under some measure: it finishes no later, covers at least as many elements, uses no more resources.

The two forms are equivalent in strength for the proofs they carry. A stays-ahead proof establishes, by induction, the same conclusion that a sequence of exchanges establishes by transformation, and an exchange argument can usually be recast as a stays-ahead comparison. Stays-ahead is usually easier to write for scheduling problems, where the measure is a completion time, and exchange is easier when the solution is a set and the repair is a set operation. Choosing between them is a matter of which invariant is easier to state, not of which is more rigorous.

One caution applies to both. The comparison must be against an optimal solution to the same remaining subproblem. Comparing a greedy prefix to a prefix of some fixed optimal solution is only valid if the optimal solution can be assumed to contain the greedy prefix, which is exactly what the exchange is supposed to prove. Circular proofs of this shape are common and read plausibly, which is why the containment obligation above is worth stating explicitly.

What the argument does not give

An exchange argument proves optimality; it says nothing about running time, and a correct greedy algorithm can still be too slow. Nor does it prove uniqueness: ties in the greedy rule usually mean several optimal solutions exist, and the proof must work for whichever tie-breaking rule the implementation uses. If the proof relies on a specific tie-break, the implementation must encode it, or the correctness claim is about a different algorithm.

The argument also assumes the input is finite and that an optimal solution exists. Both hold for the combinatorial problems discussed here. They need not hold for problems with continuous decision variables, where the greedy choice may be optimal only in a limiting sense and no first divergence exists to exchange.