Exchange Arguments

The standard way to prove a greedy algorithm optimal: assume an optimal solution, show it can be transformed step by step into the greedy one without getting worse, and conclude greedy is optimal too.

The two forms

Adjacent swap (for orderings). Take an optimal ordering. If two adjacent elements are out of greedy order, swap them and show the objective does not worsen. Since any permutation is reachable by adjacent swaps, greedy is optimal.

Exchange (for selections). Take an optimal solution differing from greedy at the first position. Replace the optimal’s choice with greedy’s choice and show the result is still feasible and no worse. Induct.

The recipe for ordering problems

To find the right sort key, consider just two jobs $i$ and $j$ and ask when $i$ should precede $j$:

$\text{cost}(i\text{ then }j)\le \text{cost}(j\text{ then }i).$

Rearrange into the form $f(i)\le f(j)$ — that inequality is the comparator.

sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
    return costIfAFirst(a, b) < costIfBFirst(a, b);      // derived pairwise
});

Check transitivity

A comparator derived this way must be a strict weak ordering. If the pairwise condition is not transitive, sorting is undefined behaviour and the greedy is wrong. Most standard keys (ratios, differences) are transitive; verify unusual ones.

The classic sort keys

Problem	Objective	Sort by
Interval scheduling	max non-overlapping	earliest finish time
Minimum max lateness	$\min \max L_j$	earliest deadline (EDD)
Minimum sum of completion times	$\min \sum C_j$	shortest processing time (SPT)
Minimum weighted sum	$\min \sum w_j{C}_j$	Smith’s rule: $p_j/w_j$ ascending
Huffman	min weighted path length	merge the two smallest
Fractional knapsack	max value	value/weight ratio
Two-machine flow shop	min makespan	Johnson’s rule
Minimise $\sum$ of $a_{i}x+b_i$ style costs	—	pairwise comparison
Minimum number of platforms	—	sort events by time
Maximise $\sum \min (a_i,b_j)$ pairings	—	sort both, pair greedily

Deriving Smith’s rule

Two jobs, $i$ before $j$: cost $=w_i{p}_i+w_j(p_i+p_j)$. Swapped: $w_j{p}_j+w_i(p_i+p_j)$. Then

$i\text{ first is better}⟺w_j{p}_i\le w_i{p}_j⟺\frac{p_i}{w_i}\le \frac{p_j}{w_j}.$

Three lines, and it gives the comparator directly. This is the whole technique.

Proving the selection form

For interval scheduling (earliest finish first):

1. Let $G=g_1,g_2,\dots$ be greedy’s choices and $O=o_1,o_2,\dots$ an optimal solution, both sorted by finish time.
2. Claim: $\mathrm{finish}(g_k)\le \mathrm{finish}(o_k)$ for all $k$. By induction: greedy picks the earliest-finishing compatible interval, and $o_k$ is compatible with $g_1..g_{k-1}$ by the hypothesis.
3. If $|O|>|G|$, then $o_{|G|+1}$ starts after $\mathrm{finish}(o_{|G|})\ge \mathrm{finish}(g_{|G|})$, so greedy could have taken it — contradicting that greedy stopped.
4. Hence $|G|=|O|$. ∎

This “greedy stays ahead” structure is the template for most selection proofs.

When greedy fails

An exchange argument that does not close is evidence the greedy is wrong. Common failures:

Problem	Greedy fails because
0/1 knapsack	items are indivisible; ratio order is not optimal
Coin change, arbitrary denominations	largest-first can be beaten ($\{1,3,4\}$, target 6)
Weighted interval scheduling	a long high-value interval may beat several short ones
Set cover	greedy is only $\ln n$-approximate
TSP	nearest neighbour is $\Theta (\log n)$-approximate
Graph colouring	greedy depends on the vertex order

Always test greedy against a brute force on small random inputs. A failing case is found in seconds and saves a wrong-answer verdict.

Matroids — when greedy is guaranteed

If the feasible sets form a matroid (closed downward, plus the exchange property), then greedy by weight is optimal for maximum-weight independent sets. This covers:

• spanning forests → Kruskal,
• linearly independent vectors → linear basis,
• partition and uniform matroids,
• scheduling unit jobs with deadlines (a transversal matroid).

Recognising a matroid is a proof that greedy works, with no exchange argument needed.

See also: Algorithmic Paradigms · Scheduling · Proof Techniques