Transforming optimal into greedy
An exchange argument is the workhorse proof technique for greedy algorithms. The idea is to take any optimal solution and repeatedly swap one of its elements for the corresponding greedy choice, showing each swap leaves the solution at least as good. After enough swaps the optimal solution becomes the greedy one, so the greedy solution must also be optimal.
The shape of the proof
- Assume an optimal solution that differs from the greedy one.
- Locate the first place they disagree.
- Argue that exchanging the optimal element there for the greedy element does not worsen the objective and keeps the solution valid.
- Repeat until no disagreements remain.
A concrete case
Consider scheduling to minimize lateness, sorted by deadline. Suppose an optimal schedule has two adjacent jobs out of deadline order. Swapping them to put the earlier deadline first cannot increase the maximum lateness, because the swapped pair finishes no later than before. Each such swap moves the optimal schedule one step toward the greedy ordering without harm, so the greedy ordering is optimal. The two variants are an exchange style, which swaps elements, and a stays ahead style, which shows greedy is never behind optimal at any step.
Key idea
An exchange argument proves a greedy algorithm optimal by swapping each differing element of an arbitrary optimal solution toward the greedy choice without worsening the objective, until the optimal solution becomes the greedy one.