Algorithms / Greedy Exchange Arguments
Least You Need to Know: Greedy Choice, Exchange Arguments, and Local Decisions
Greedy algorithms succeed when a **locally optimal step** can be justified as part of some globally optimal solution. Exchange arguments and staying-ahead arguments explain why taking a certain next move never makes the final answer worse.
The least you need to know
- A greedy algorithm makes one irrevocable local choice and then continues on the reduced problem.
- The key proof question is not speed but correctness: why is that local choice always safe?
- An exchange argument shows an optimal solution can be transformed to use the greedy choice without losing quality.
- A heuristic can look reasonable and still fail if there is no safety argument behind it.
- Greedy correctness usually depends on structure in the problem, not just intuition.
Key notation
greedy choice
next local step taken immediately
exchange argument
swap optimal solution pieces to include greedy step
stays ahead
greedy partial solution is never worse than competitors so far
Tiny worked example
- In interval scheduling, pick the interval that finishes earliest.
- If an optimal schedule starts with a later-finishing interval, swap that first interval with the greedy one.
- The greedy interval leaves at least as much room for the remaining intervals.
- So there exists an optimal schedule that begins with the greedy choice.
Common mistakes
- Students often call a method greedy just because it is fast, even without a proof that the local choice is safe.
- Students often confuse 'works on examples' with a correctness argument.
- Students often forget that some coin systems and scheduling rules break greedy intuition.
How to recognize this kind of problem
- The problem can be reduced after one safe local choice.
- There is a natural candidate for an exchange or staying-ahead proof.
- You want one good optimum, not all valid combinations.