Greedy algorithm

Lore & Background

Greedy algorithms are widely used in computer science and mathematics. Classic examples include Huffman coding, Prim's algorithm, Kruskal's algorithm, and Dijkstra's algorithm, all of which use greedy properties. Mathematicians also employ greedy strategies in proofs, such as the greedy proof that every tournament contains a Hamiltonian path. The activity selection problem admits an exact greedy solution: sorting tasks by end time and repeatedly choosing the first task that begins after the last task ended.

Reader's Guide

Greedy algorithms are significant because they provide efficient solutions to many optimization problems, though they are not always optimal. Their correctness is often proven using an exchange argument, which shows that any solution different from the greedy solution is at most as good. The characterization of when a problem admits a greedy solution is not fully known, but special cases have been identified, such as problems with a matroid structure (Jack Edmonds) or a greedoid structure (Bernhard Korte and László Lovász). Greedy algorithms are also used for approximation, as in the travelling salesman problem, the 0-1 knapsack problem, and submodular maximization. Their legacy includes foundational algorithms in graph theory, network routing, and signal approximation.

Did You Know?

• A greedy algorithm is a special case of a dynamic programming algorithm, according to Uriel Feige.
• The Gale-Shapley algorithm is not greedy because it may modify existing solutions.
• A greedy algorithm finds the optimal solution to Malfatti's problem of finding three disjoint circles within a triangle.
• Fibonacci described a greedy algorithm for computing Egyptian fractions.