Greedy Algorithm

A greedy algorithm is a constructive algorithm class that makes the locally optimal-looking decision at every step and never backtracks. Its roots trace to classic combinatorial work (Kruskal 1956 and Prim 1957 for minimum spanning tree; Dijkstra 1959 for shortest path). When the greedy approach yields the global optimum is characterized by matroid theory: the Rado-Edmonds theorem (Edmonds 1971) states that a subset system is solved optimally by the greedy algorithm for all weight functions if and only if it is a matroid. This is why minimum spanning tree (Kruskal/Prim), Huffman coding (Huffman 1952), and single-machine weighted-completion-time (SPT/EDD rules, Smith 1956) admit greedy optimum solutions. By contrast, knapsack, bin packing, set covering, and VRP have greedy solutions bounded only within a known approximation factor (e.g. Chvátal 1979 ln(n)+1 for set covering) and are not globally optimal. In practice greedy algorithms play three roles: (1) fast constructive heuristic (warm-start), (2) approximation algorithm guarantee family, (3) initial solution for local search or metaheuristics. Heuristically the greedy TSP (nearest neighbor), the Clarke-Wright savings method (1964) for VRP, and the LPT/SPT family for scheduling are industry-standard examples. Cormen, Leiserson, Rivest and Stein (CLRS, 2009) chapter 16 is the reference treatment.