Greedy Algorithms
Make the locally-best choice; prove it with an exchange argument.
The idea
A greedy algorithm builds a solution one piece at a time, following a fixed local rule that ranks the available choices.
Algorithm.
Algorithm: Generic Greedy Loop Input: a set of candidate pieces, a local rule that ranks them Output: a feasible solution assembled piece by piece 1. start with the empty solution 2. among the candidates that keep the solution feasible, take the one the rule ranks best 3. commit: add it to the solution, never reconsider it 4. if some candidate can still be added, go to step 2 5. return the solution built
The result is very fast — typically one sort followed by a single pass, $O(n \log n)$ in total — but for most rules it is not optimal, because the choice that looks best now need not belong to any best solution overall.
A greedy rule therefore requires a proof of correctness: a demonstration that never reconsidering costs nothing, because the locally best choice is compatible with some globally optimal solution. The standard proof is an exchange argument. Take any optimal solution and swap the greedy choice into it, in place of whatever that solution did first. If the result is always still feasible and still optimal, then some optimal solution begins with the greedy choice, and repeating the argument on the remaining subproblem shows that the greedy solution matches the optimum.
The design question is the choice of rule. For a given problem, several plausible rules can each look right on small examples, and testing examples cannot separate a rule that usually works from one that is provably optimal. Only the exchange argument settles it.
Ways to work on it
- Walkthrough. The greedy choice, activity selection by earliest finish, and the exchange-argument proof.
- Practice. Run earliest-finish-time greedy on a small instance.
- Hardest. Compare a wrong greedy rule against earliest-finish-time and see why correctness needs proof.
Not sure where to start? Take the ten-question placement test.