Exchange Arguments for Correctness
You'll learn how to prove a greedy algorithm is optimal by showing you can swap any non-greedy choice with a greedy one without making things worse.
The Core Idea
An exchange argument is a proof technique that validates greedy algorithms. Here's how it works:
- Assume there's an optimal solution that differs from your greedy solution
- Find the first place where they disagree
- Show you can "exchange" the non-greedy choice with the greedy choice
- Prove this exchange doesn't worsen the solution (and often equals or improves it)
- Repeat until you've transformed the optimal solution into your greedy solution
- Conclude: if you can reach any optimal solution through safe exchanges, your greedy solution must also be optimal
A Practical Example
Think of the Activity Selection Problem (choosing non-overlapping activities). Your greedy strategy picks the activity that finishes earliest.
Suppose someone claims a different selection is optimal. Find the first activity where you disagree—maybe they chose activity B while you chose activity A (which finishes earlier).
The exchange: Swap their choice B for your choice A. Since A finishes earlier, it can't conflict with any activities that B allowed. You've made an exchange without losing any future opportunities. The solution quality stays the same or improves.
Keep exchanging until their solution matches yours. Since we never made things worse, your greedy solution must be optimal too!
Why This Matters
Exchange arguments don't just prove correctness—they reveal why the greedy choice is safe. They show that greedily picking what seems best locally never blocks you from reaching a globally optimal solution.
Key Takeaway: Exchange arguments prove greedy correctness by demonstrating that any optimal solution can be transformed into your greedy solution through a series of swaps that never worsen the result.