Chapter notes

Much more material on greedy algorithms and matroids can be found in Lawler [196] and Papadimitriou and Steiglitz [237].

The greedy algorithm first appeared in the combinatorial optimization literature in a 1971 article by Edmonds [85], though the theory of matroids dates back to a 1935 article by Whitney [314].

Our proof of the correctness of the greedy algorithm for the activity-selection problem is based on that of Gavril [112]. The task-scheduling problem is studied in Lawler [196], Horowitz and Sahni [157], and Brassard and Bratley [47].

Huffman codes were invented in 1952 [162]; Lelewer and Hirschberg [200] surveys data-compression techniques known as of 1987.

An extension of matroid theory to greedoid theory was pioneered by Korte and Lovász [189, 190, 191, 192], who greatly generalize the theory presented here.