Chapter 4: Greedy Algorithms

“Greed…is good. Greed is right. Greed works.” - Michael Douglas.

An algorithm is greedy if it builds up a solution in small steps, choosing a decision at each step myopically to optimize some underlying criterion. When a greedy algorithm succeeds there is a local decision rule that one can use to construct optimal solutions. There are two basic methods that we will follow for proving that a greedy algorithm produces an optimal solution to a problem. One can view the first approach as establishing that the greedy algorithm stays ahead. The second approach is known as an exchange argument.

We will run through a few of the most well-known applications of greedy algorithms: shortest paths in a graph, the Minimum Spanning Tree Problem, and the construction of Huffman codes for performing data compression. Also a more complex application will be considered, the Minimum-Cost Arborescence Problem.