Greedy Strategy and Its Limits¶

Locally optimal choices yield globally optimal solutions only when the problem has the greedy choice property (local best never blocks global best) and optimal substructure.

Tension Addressed¶

Simplicity vs. Optimality

Recognizable As¶

Single-pass algorithms that commit to choices without backtracking; matroid structure; exchange arguments in correctness proofs.

Canonical Sources¶

Huffman, "A Method for the Construction of Minimum-Redundancy Codes," 1952; Kruskal/Prim MST; Kleinberg & Tardos, Algorithm Design, Chapter 4

Transfers To¶

Scheduling, resource allocation, compression, network design, approximation algorithms

Greedy algorithms are powerful when they work but dangerous when applied without proof. The concept of "exchange argument" (proving any non-greedy solution can be improved by swapping) is the canonical verification technique.