Greedy Algorithms
A greedy algorithm commits to one locally preferred choice without revisiting it. This is correct only when the problem structure proves that some optimal solution contains that choice.
Design workflow
- Define feasible solutions and the objective precisely.
- State the local choice rule and what remains afterward.
- Prove the choice is safe.
- Show the residual problem has the same structure.
- Derive complexity from selection and update data structures.
Common proof patterns
- Exchange argument: replace part of an optimal solution with the greedy choice without making it worse.
- Stays ahead: after every prefix of choices, greedy is at least as good as any competitor under a useful measure.
- Cut property: a locally light edge is safe across a suitable partition.
- Induction: after proving the first safe choice, apply the same reasoning to the residual instance.
Representative problems
| Problem | Safe choice | Required structure |
|---|---|---|
| Activity selection | earliest finish | maximize count of compatible intervals |
| Fractional knapsack | highest value density | divisible items, linear value |
| Huffman coding | merge two least frequent nodes | binary prefix-code objective |
| MST | safe light edge across a cut | weighted undirected graph |
| Dijkstra | settle minimum tentative distance | nonnegative edge weights |
Greedy coin selection, highest immediate profit, or smallest immediate cost can fail on arbitrary instances. A plausible rule is a conjecture until a proof or known structural theorem supports it.
Greedy versus dynamic programming
Dynamic programming compares alternatives across reusable states. Greedy collapses those alternatives using a safe-choice theorem. When the exchange property fails, retaining more state may be necessary.