Intuition The one-sentence ideaAn exchange argument proves a greedy algorithm is optimal by showing: take ANY optimal solution, and you can swap (exchange) one of its choices for the greedy choice without making the solution worse . Repeat until the optimal solution looks exactly like the greedy one. Since greedy ≤ optimal at every swap and we never lose quality, greedy must itself be optimal.
Definition Exchange argumentA proof technique for greedy correctness. Let G G G O O O optimal solution. We find the first place where they differ , then show we can modify O O O G G G while keeping O O O O O O G G G G G G
There are two flavours you must recognise:
Greedy-stays-ahead — show greedy is never behind optimal after k k k Exchange/swap — physically swap two elements in O O O
This note is about the swap flavour, the workhorse for ordering/scheduling problems.
Intuition Why "no worse after a swap" is enoughSuppose every optimal O O O still feasible , (b) is no worse , and (c) agrees with greedy in one more place . Then start from O O O G G G G G G
The deep reason: you are building a chain
O = O 0 → O 1 → ⋯ → O m = G , cost ( O i + 1 ) ≤ cost ( O i ) . O = O_0 \;\to\; O_1 \;\to\; \cdots \;\to\; O_m = G,\qquad \text{cost}(O_{i+1}) \le \text{cost}(O_i). O = O 0 → O 1 → ⋯ → O m = G , cost ( O i + 1 ) ≤ cost ( O i ) . cost ( G ) ≤ cost ( O ) = OPT \text{cost}(G) \le \text{cost}(O) = \text{OPT} cost ( G ) ≤ cost ( O ) = OPT OPT \text{OPT} OPT cost ( G ) = OPT \text{cost}(G) = \text{OPT} cost ( G ) = OPT
The whole game lives in step 5 — and it always boils down to the inequality that defines the greedy choice.
Problem. n n n k k k p k p_k p k (unweighted) total completion time ∑ k C k \sum_k C_k ∑ k C k C k C_k C k k k k Shortest Processing Time first (SPT) . (If each job also had a weight w k w_k w k ∑ k w k C k \sum_k w_k C_k ∑ k w k C k p k / w k p_k/w_k p k / w k
Worked example Exchange proof for SPTSetup. Let O O O O O O a a a b b b p a > p b p_a > p_b p a > p b
Swap. Swap a a a b b b O O O O ′ O' O ′ Why this step? All jobs scheduled before a a a b b b C a , C b C_a, C_b C a , C b
Let t t t
In O O O C a = t + p a C_a = t+p_a C a = t + p a C b = t + p a + p b C_b = t+p_a+p_b C b = t + p a + p b = 2 t + 2 p a + p b = 2t+2p_a+p_b = 2 t + 2 p a + p b
In O ′ O' O ′ C b = t + p b C_b = t+p_b C b = t + p b C a = t + p b + p a C_a = t+p_b+p_a C a = t + p b + p a = 2 t + 2 p b + p a = 2t+2p_b+p_a = 2 t + 2 p b + p a
Why this step? The job that finishes second pays the other's length, so putting the shorter job first reduces the doubled term.
Difference: cost ( O ) − cost ( O ′ ) = ( 2 p a + p b ) − ( 2 p b + p a ) = p a − p b > 0. \text{cost}(O)-\text{cost}(O') = (2p_a+p_b)-(2p_b+p_a) = p_a-p_b > 0. cost ( O ) − cost ( O ′ ) = ( 2 p a + p b ) − ( 2 p b + p a ) = p a − p b > 0.
So O ′ O' O ′ strictly better — contradicting optimality unless no inversion existed. Hence optimal has no inversions, i.e. it's sorted by SPT. ∎
Problem. Intervals [ s k , f k ) [s_k,f_k) [ s k , f k ) earliest finish time .
Worked example Exchange proofSetup. Let O = ( o 1 , o 2 , … ) O=(o_1,o_2,\dots) O = ( o 1 , o 2 , … ) g 1 g_1 g 1
Claim/Swap. Replace o 1 o_1 o 1 g 1 g_1 g 1 O ′ O' O ′
Why this step? g 1 g_1 g 1 o 1 o_1 o 1 f g 1 ≤ f o 1 f_{g_1}\le f_{o_1} f g 1 ≤ f o 1 g 1 g_1 g 1 o 1 o_1 o 1 g 1 g_1 g 1 feasibility is preserved .
Why no worse? O ′ O' O ′ same number of activities as O O O O ′ O' O ′
Induct on the remaining subproblem (activities starting after f g 1 f_{g_1} f g 1
Note the contrast with Example 1: here the swap gives equal cost (counting problem), there it gave strict improvement. Both are valid exchange arguments.
Worked example The "two least frequent are siblings" exchangeClaim. In some optimal prefix tree, the two lowest-frequency symbols x , y x,y x , y
Setup. Take optimal tree T T T a , b a,b a , b f ( x ) ≤ f ( y ) f(x)\le f(y) f ( x ) ≤ f ( y ) f ( a ) ≤ f ( b ) f(a)\le f(b) f ( a ) ≤ f ( b ) f ( x ) , f ( y ) f(x),f(y) f ( x ) , f ( y ) f ( x ) ≤ f ( a ) f(x)\le f(a) f ( x ) ≤ f ( a ) f ( y ) ≤ f ( b ) f(y)\le f(b) f ( y ) ≤ f ( b ) d x = depth ( x ) d_x=\text{depth}(x) d x = depth ( x )
Swap. Exchange x ↔ a x\leftrightarrow a x ↔ a and y ↔ b y\leftrightarrow b y ↔ b two swaps, so the cost change is the sum of two terms , one per swap.
Why no worse? Cost = ∑ f ( c ) depth ( c ) = \sum f(c)\,\text{depth}(c) = ∑ f ( c ) depth ( c ) x ↔ a x\leftrightarrow a x ↔ a ( f ( a ) − f ( x ) ) ( d x − d a ) (f(a)-f(x))(d_x-d_a) ( f ( a ) − f ( x )) ( d x − d a ) y ↔ b y\leftrightarrow b y ↔ b ( f ( b ) − f ( y ) ) ( d y − d b ) (f(b)-f(y))(d_y-d_b) ( f ( b ) − f ( y )) ( d y − d b ) total change is
Δ = ( f ( a ) − f ( x ) ) ( d x − d a ) + ( f ( b ) − f ( y ) ) ( d y − d b ) . \Delta = (f(a)-f(x))(d_x-d_a) + (f(b)-f(y))(d_y-d_b). Δ = ( f ( a ) − f ( x )) ( d x − d a ) + ( f ( b ) − f ( y )) ( d y − d b ) . Why this step? You must add both terms — accounting for only one swap would be incomplete.
Each term is ≤ 0 \le 0 ≤ 0 f ( a ) ≥ f ( x ) f(a)\ge f(x) f ( a ) ≥ f ( x ) a a a d a ≥ d x d_a\ge d_x d a ≥ d x × \times × ≤ 0 \le 0 ≤ 0 f ( b ) ≥ f ( y ) f(b)\ge f(y) f ( b ) ≥ f ( y ) d b ≥ d y d_b\ge d_y d b ≥ d y Δ ≤ 0 \Delta\le 0 Δ ≤ 0
Common mistake "Greedy works because it's locally best, so I don't need a proof."Why it feels right: locally optimal moves often do win, and it's tempting to trust the pattern. The fix: locally best ≠ globally best (e.g. coin change with denominations { 1 , 3 , 4 } \{1,3,4\} { 1 , 3 , 4 } 6 6 6 4 + 1 + 1 = 3 4+1+1=3 4 + 1 + 1 = 3 3 + 3 = 2 3+3=2 3 + 3 = 2 certifies greedy — without it you have a heuristic, not a proof.
Common mistake "Sort by processing time always minimises completion-time objectives."Why it feels right: SPT is correct for the unweighted ∑ C k \sum C_k ∑ C k The fix: for weighted completion time ∑ w k C k \sum w_k C_k ∑ w k C k a , b a,b a , b w b p a − w a p b w_b p_a - w_a p_b w b p a − w a p b p a / w a ≥ p b / w b p_a/w_a \ge p_b/w_b p a / w a ≥ p b / w b ratio p k / w k p_k/w_k p k / w k (Smith's rule), not by p k p_k p k w k = 1 w_k=1 w k = 1
Common mistake Forgetting to checkfeasibility after the swap.
Why it feels right: we focus on the cost inequality and assume the swapped solution is still valid. The fix: every exchange proof has two obligations — (1) O ′ O' O ′ O ′ O' O ′
Common mistake Swapping at the wrong place (arbitrary index instead of thefirst difference).
Why it feels right: any difference looks swappable. The fix: you must swap at the first disagreement and use induction on the prefix that already matches greedy , otherwise you can't guarantee termination toward G G G
Common mistake Accounting for only one swap when the proof does two (e.g. Huffman).Why it feels right: the first swap's inequality looks like the whole story. The fix: if the construction performs two exchanges (x ↔ a x\leftrightarrow a x ↔ a y ↔ b y\leftrightarrow b y ↔ b sum of both terms; you must show the combined expression is ≤ 0 \le 0 ≤ 0
Recall Feynman: explain to a 12-year-oldImagine the best possible way to line up kids by who finishes a chore fastest. I show you my "always-pick-the-quickest-next" plan. You say "but the real best plan might be different!" So I take your supposed best plan, find the first spot where it disagrees with mine, and swap two kids . I prove the total waiting time doesn't go up after the swap. I keep swapping until your plan looks exactly like mine — and since I never made it worse, my simple plan was the best all along. That swapping trick is the exchange argument.
Mnemonic Remember the recipe"First Find Twin, Swap, Show" → FFTSS : find the First difference, Find the Twin of greedy's element in O O O Swap it in, Show cost doesn't rise. (Pun: FaT SwapS keep the proof healthy.)
What does an exchange argument transform, and into what? Any optimal solution
O O O , into greedy's solution
G G G , via a chain of swaps that never increases cost.
What are the TWO obligations after every swap? (1) The swapped solution stays feasible; (2) its cost is no worse than before.
In the SPT proof, what is cost( O ) − (O)- ( O ) − ( O ′ ) (O') ( O ′ ) a a a b b b p a − p b > 0 p_a-p_b>0 p a − p b > 0 (longer-before-shorter is strictly worse) — for the
unweighted ∑ C k \sum C_k ∑ C k .
For weighted completion time ∑ w k C k \sum w_k C_k ∑ w k C k Sort by the ratio
p k / w k p_k/w_k p k / w k (Smith's rule); SPT is the special case
w k = 1 w_k=1 w k = 1 .
Why must you swap at the FIRST index where G G G O O O To induct on the matching prefix and guarantee the swaps converge to
G G G in finitely many steps.
Counting problems (activity selection) give which kind of inequality after the swap? Equality (same number of activities) — you show an optimal solution matches greedy, not strict improvement.
Give a denomination set where greedy coin change fails. { 1 , 3 , 4 } \{1,3,4\} { 1 , 3 , 4 } making
6 6 6 : greedy =
4 + 1 + 1 4+1+1 4 + 1 + 1 (3 coins), optimal =
3 + 3 3+3 3 + 3 (2 coins).
In activity selection, why does replacing o 1 o_1 o 1 g 1 g_1 g 1 f g 1 ≤ f o 1 f_{g_1}\le f_{o_1} f g 1 ≤ f o 1 , so any later activity compatible with
o 1 o_1 o 1 is still compatible with
g 1 g_1 g 1 .
What telescoping inequality finishes an exchange proof? cost
( G ) ≤ (G)\le ( G ) ≤ cost
( O ) = (O)= ( O ) = OPT, so cost
( G ) = (G)= ( G ) = OPT.
In Huffman's sibling lemma, why is the total cost change ≤ 0 \le 0 ≤ 0 It is the SUM of two swap terms
( f ( a ) − f ( x ) ) ( d x − d a ) + ( f ( b ) − f ( y ) ) ( d y − d b ) (f(a)-f(x))(d_x-d_a)+(f(b)-f(y))(d_y-d_b) ( f ( a ) − f ( x )) ( d x − d a ) + ( f ( b ) − f ( y )) ( d y − d b ) , each a (non-neg)
× \times × (non-pos) product.
Greedy Algorithms — general paradigm Greedy-stays-ahead proof technique Activity Selection Problem Huffman Coding Scheduling to minimise completion time Smith's rule — weighted completion time Matroids and the greedy theorem (the algebraic reason exchange works for whole classes of problems)Proof by contradiction and Induction Dynamic Programming (what to use when no exchange argument exists)
First difference at index i
Swap oi and oj into O prime
Telescoping cost G <= OPT
SPT example minimise sum Ck
Intuition Hinglish mein samjhoDekho, greedy algorithm me hum har step pe "abhi ke liye sabse best" choice utha lete hain — jaise jobs ko sabse chhoti length wali pehle chalao, ya activities me jo sabse jaldi khatam ho usko pehle pakdo. Par sawaal yeh hai: kya yeh local lalach (greed) globally best answer dega? Iska proof dena padta hai, warna woh sirf ek heuristic hai. Exchange argument exactly yahi proof technique hai.
Idea simple hai: maan lo koi optimal solution O O O first jagah dhoondo jahan dono differ karte hain. Wahan pe greedy ki choice ko O O O swap kar do. Ab tumhe do cheezein prove karni hain — (1) swap ke baad solution abhi bhi valid (feasible) hai, aur (2) uska cost pehle se kharab nahi hua. Agar yeh ho gaya, to ek-ek swap karte karte O O O G G G ( G ) ≤ (G) \le ( G ) ≤ ( O ) = (O) = ( O ) =
SPT example me, jab objective sirf ∑ C k \sum C_k ∑ C k p a − p b p_a - p_b p a − p b w k w_k w k ∑ w k C k \sum w_k C_k ∑ w k C k p k / w k p_k/w_k p k / w k p k p_k p k x ↔ a x\leftrightarrow a x ↔ a y ↔ b y\leftrightarrow b y ↔ b sum ≤ 0 \le 0 ≤ 0
Yaad rakho do common galtiyan: feasibility check bhulna mat, aur hamesha first difference pe swap karna, kisi bhi random jagah nahi. Counting problems me "<" ke chakkar mat pado, "≤" enough hai. Mnemonic: FFTSS — First difference, Find Twin, Swap, Show cost-no-worse. Bas yeh recipe ratt lo, koi bhi greedy proof crack ho jaayega.
