Greedy Strategy¶

Making locally optimal choices at each step sometimes yields globally optimal solutions; when it works, greedy algorithms are simpler and faster than alternatives requiring global consideration.

Tension Addressed¶

Optimality vs. Simplicity (trades guaranteed optimality for simplicity)

Recognizable As¶

Huffman coding, minimum spanning trees, activity selection, coin change (when it works), packet scheduling, resource allocation heuristics

Canonical Sources¶

Edmonds, Matroids and the Greedy Algorithm (1971); CLRS, Introduction to Algorithms (Greedy Algorithms chapter)

Transfers To¶

Economic decision-making, scheduling systems, network routing, compression algorithms, resource allocation

Sub-concepts: - Greedy choice property: Local optimum leads to global optimum - Matroid structure: Mathematical foundation for when greedy works - Greedy failure modes: Knowing when local optimization misleads