Greedy algorithm

Key characteristics

Two informal properties explain when greedy strategies tend to succeed: the greedy-choice property, meaning a local choice can be extended to an optimal global solution, and optimal substructure, meaning an optimal solution to the whole contains optimal solutions to subproblems. Greedy methods typically run fast, require little memory, and are easy to implement.

Theory and history

Greedy ideas appear across algorithmic history and underpin many classical algorithms. Theoretical work has identified problem families (for example, matroids) where greedy selection always yields an optimal result. When exact optimality is impossible, greedy rules can often be analyzed to provide approximation guarantees and are common in the design of efficient heuristics.

Common examples and applications

• Fractional knapsack: select items by value-per-weight to maximize value when partial items are allowed.
• Huffman coding: build optimal prefix codes by repeatedly combining least-frequent symbols.
• Minimum spanning trees: Prim's and Kruskal's algorithms choose smallest edges greedily to connect components.
• Shortest paths with nonnegative edges: Dijkstra's algorithm picks the nearest unsettled node next.
• Scheduling and selection problems: activity selection picks earliest-finishing tasks first.

Limits, proofs and approximations

Greedy methods do not always succeed: the 0/1 knapsack problem and some coin systems give counterexamples where the greedy choice is suboptimal. Proofs of correctness usually use an exchange argument or induction to show any optimal solution can be transformed to one produced by the greedy rule without loss. For problems where greedy cannot reach optimality, it can still produce useful approximations; for instance, the greedy algorithm for set cover yields a logarithmic-factor approximation. For more detailed treatments and proofs see further reading.