Algorithms / Greedy Exchange Arguments
Least You Need to Know: Greedy Proofs via Exchange Arguments
An exchange argument proves a greedy algorithm by showing that some optimal solution can be modified step by step to agree with the greedy choice without getting worse. The core idea is not that the greedy step 'feels good,' but that a formal swap preserves feasibility and objective value or improves it.
The least you need to know
- An exchange argument starts from an optimal solution and transforms it to include the greedy choice.
- The swap must preserve feasibility.
- The swap must not worsen the objective.
- This proves that at least one optimal solution can agree with the greedy step.
- Exchange arguments justify correctness; they are not just intuition.
Key notation
exchange
replace part of an optimal solution with the greedy choice
feasible
still satisfies all problem constraints after the swap
optimal
achieves the best objective value
Tiny worked example
- Suppose a greedy algorithm picks the interval with earliest finishing time.
- Take any optimal schedule.
- If its first interval is different, swap in the greedy interval.
- Because the greedy interval finishes no later, the remaining schedule still fits.
- So there exists an optimal schedule starting with the greedy choice.
Common mistakes
- A swap that improves one local property but breaks feasibility is not a valid exchange argument.
- The proof target is usually existence of an optimal solution compatible with the greedy choice.
- Exchange arguments are especially common in scheduling and spanning-tree proofs.
How to recognize this kind of problem
- The proof tries to replace one choice in an optimal solution with the greedy choice.
- You need to show both feasibility preservation and no worse objective.
- The wording often includes 'without loss of optimality' after the swap.